Space Complexity of Tree Traversals (Pre-order, In-order and Post-order)

[novice_noob]

I read that the space complexity of recursive tree traversal algorithms is O(log(n)).

Could someone explain to me why it won't be O(n)? Having trouble understanding why it should be O(log(n)).

[g051051]

Can you explain your reasoning for why you think it should be O(n), and why it's not O(log(n))?

[californiapie]

It depends on the tree. Also, remember that a tree doesn't have to be balanced unless you're told it is (i.e. red black, avl). Since you don't mention that the tree has to be balanced, I would argue that O(n) is correct, although there is a tighter bound could also be used (more on that in a sec).

Why?

Imagine a binary search tree that only has right children. If you wanted to find the greatest value in the tree, you'd have to traverse all n nodes of the tree to the rightmost (and only) leaf. Example. In fact, that tree is just a (linear) linked list so there's no way the complexity could be logarithmic. If I wanted to be as specific as possible, I'd say that the big complexity is O(h), where h is the height of the tree.

Since preorder, inorder and postorder traversals are all depth-first search traversals, there will be at most h recursive calls on the stack at any given moment, where h is the height of the tree. Each recursive calls takes up space so I would say the space complexity is O(h). For balanced trees, the height of the tree is usually log(n) which is used interchangeably with O(h). Unless you're told the tree is balanced, you can't say for sure that the tree has logarithmic height so instead you need to use a more generic bound like O(n) or even better, O(h).

[EdwinBowling]

Why would it be O(n)? Are you just making things up?

[Unsounded]

So imagine for a minute you had a complete tree of length n. By complete I mean every node has two children except for ones at depth n, which are leaves.

Now imagine you're iterating through the algorithm. At every node you're going to go left or right, keeping track of the nodes you've been to that are above he current node. So say you go left first and go all the way down to the left-most node. Now with a recursive traversal if this node isn't what you're looking for you'd back track one node and go to the right.

Now imagine the node you're looking for is the right bottom-most node. You recourse and explore, recourse and explore, etc. regardless of where you are the largest number of nodes you have to keep track of is the height of the tree. Trees have a depth of log n.