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 →
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.