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