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?
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).