def height(node):
if not node:
return -1 # an empty subtree has height -1
left = height(node.left)
right = height(node.right)
return max(left, right) + 1
Trace it on the tree above and watch every node wait for its children before it can answer.
Node 7: leaf -> 0
Node 4: left(7)=0, no right -> max(0, -1) + 1 = 1
Node 5: leaf -> 0
Node 2: left(4)=1, right(5)=0 -> max(1, 0) + 1 = 2
Node 6: leaf -> 0
Node 3: no left, right(6)=0 -> max(-1, 0) + 1 = 1
Node 1: left(2)=2, right(3)=1 -> max(2, 1) + 1 = 3
Try the same thing with preorder and you hit the parent first, with no information about the subtree below it. You can still make it work by passing depth down as a parameter and tracking a maximum in an outer variable, but it is fifteen awkward lines where postorder is five. Diameter, subtree sums, balanced checks, distributing coins: same shape every time. The parent cannot answer until both children have reported back, so you process the children first.
The first time I had to write any of these iteratively under a timer, I realized I had memorized the recursion and never the stack sitting under it. That gap is part of why I built Codeintuition, and the binary tree course traces the stack state for the iterative versions one frame at a time.
Level order is the odd one out
Level order is the only one that is not depth first. It uses a queue, not the call stack. Enqueue the root, then repeatedly dequeue a node and enqueue its children. Nodes come out one full level at a time.
from collections import deque
def level_order(root):
if not root:
return
queue = deque([root])
while queue:
node = queue.popleft()
process(node)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
Anything that works on nodes at the same depth (level sums, zigzag traversal, connecting nodes across a level) needs this breadth first access. Forcing depth first to do the same job means tracking depth by hand, which is more bookkeeping than the problem deserves.
Picking the order: which way does the data flow?
Almost every tree problem opens with the same hidden question. Does the parent need answers from its children, or do the children need data handed down from the parent? Answer that and the order falls out.
-
Postorder: the parent needs results from both children (height, diameter, subtree sums, balanced checks)
-
Preorder: the children need data passed down from the parent (root to leaf path sums, serialization)
-
Inorder: you want values in sorted order out of a BST
-
Level order: the work happens per level (level sums, zigzag, connecting same depth nodes)
A quick aside worth its own paragraph: there is a real argument that some problems read fine in more than one order, and reconstructing a tree from traversals is its own rabbit hole (preorder alone is not enough, you need inorder too, or null markers). That is a separate post. For the day to day of picking an order on sight, the data direction question settles it.
Listing the four orders is the easy part of this topic. Looking at an unfamiliar tree problem and knowing which order hands you the right information before you write a line is the skill that actually transfers to an interview, and it comes from understanding why each order exists, not from re-reading the traces.
I wrote a longer version on my own blog that walks through the iterative conversions for all three depth first orders.
Which traversal order was the one that finally made sense to you only after you got burned picking the wrong one on a real problem?