Are time complexity of pre-order and DFS on a balanced binary tree same?

Question

I read from an answer that pre-order is a type of DFS:link

Yet,for a balanced binary tree,the time complexity for a tree-traversal is O(logn)link and the DFS has a time complexity of O(N)link.

So, is pre-order traversal not a type of DFS or I misunderstood the concept?

Thanks.

Answer 1

The time complexity for a preorder, inorder, or postorder traversal of a binary search tree is always Θ(n), where is the number of nodes in the tree. One way to see this is that in each case, each node is visited once and exactly once, and each edge is visited exactly twice (once descending downward, and once ascending upward).

You had mentioned in your question that the time complexity of a tree traversal on a balanced tree is O(log n). The O(log n) here actually refers to the space complexity (how much auxiliary memory is needed) rather than the time complexity (how many operations will be performed). The reason for this is that all of these tree traversals, in their typical implementation, need to store a stack of the nodes that have been visited so far so that the traversal can back up higher in the tree when necessary. This means that the auxiliary space needed is proportional to the height of the tree, which in a balanced tree is O(log n) and in an arbitrary BST will be O(n).

So in that sense, the best answer to your question is probably "DFS, inorder traversals, preorder traversals, and postorder traversals of a BST always take the same amount of time (Θ(n)), and the space complexity depends on the height of the tree, which can range between Θ(log n) and Θ(n)."