We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Time complexity at worst case would be O(N2). You have at least one nested loop. However, the worst issue with this code is not the time or space complexity, but its cyclomatic complexity since that is what will create the greatest problem with maintaining the code.
I don't think so, because each node is travelled through at most 3 times (see https://stackoverflow.com/a/53608069/1357094). And accordingly, O(3n) = O(n) when analyzing time complexity (3n & n are both equivalent "linear" complexity).
Tree: Preorder Traversal
You are viewing a single comment's thread. Return to all comments →
Hey I'm not that sure either but this link says its O(n)
https://stackoverflow.com/questions/6478063/how-is-the-complexity-of-morris-traversal-on
Hey there. My comment says it's O(1) space complexity. The time complexity is not O(1)
Oh sorry, thanks for the clarification
here is problem solution in python java c++ and c programming. https://solution.programmingoneonone.com/2020/07/hackerrank-tree-preorder-traversal-solution.html
here is problem solution in python java c++ and c programming. https://code.programmingoneonone.com/2020/09/hackerrank-tree-preorder-traversal-solution.html
Time complexity at worst case would be O(N2). You have at least one nested loop. However, the worst issue with this code is not the time or space complexity, but its cyclomatic complexity since that is what will create the greatest problem with maintaining the code.
I don't think so, because each node is travelled through at most 3 times (see https://stackoverflow.com/a/53608069/1357094). And accordingly, O(3n) = O(n) when analyzing time complexity (3n & n are both equivalent "linear" complexity).
Thanks for providing that link. See also https://cs.stackexchange.com/questions/16833/can-a-tree-be-traversed-without-recursion-stack-or-queue-and-just-a-handful-o
Personally, I enjoyed reading part of the "Morris's Tree Traversal Algorithm Reconsidered" paper.
here is problem solution in java python c++ and c programming. https://programs.programmingoneonone.com/2021/05/hackerrank-tree-preorder-traversal-solution.html