Tree: Preorder Traversal

  • + 1 comment

    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.

    • + 2 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).

      • + 0 comments

        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.