What would be the time and space complexity of a non-binary tree traversal algorithm that prints out every possible path in the tree starting from the root?
1
-
Depends on the traversal. But depth first search would do the job and hence can be done in the order of O(N) where N is number of nodes.SomeDude– SomeDude2021-06-08 16:27:11 +00:00Commented Jun 8, 2021 at 16:27
Add a comment
|
1 Answer
In case of binary trees, the #edges = #vertices - 1. The traversal takes O(|E|) or O(|V|) time.
In case of non-binary trees, #edges = #vertices - 1 still holds true. So, traversal still takes O(|E|) or O(|V|) time.
Getting every possible path takes same amount of time as traversal = O(|E|) or O(|V|).
If you want to print all the stored paths, it could take O(length of the longest path * number of paths).
Total time complexity =Traversal + Print = O(|E|) + O(length of the longest path * number of paths).
answered Jun 8, 2021 at 16:26
Shridhar R Kulkarni
7,1563 gold badges40 silver badges64 bronze badges
1 Comment
Ante Grgurević
Thank you so much for the detailed explanation!