Skip to content

3. Depth vs height (down vs up)

Big idea: depth is about what's above a node, so it's known on the way down and passed to children as an argument. Height is about what's below a node, so it's only known on the way back up, from children's return values.

Two measurements that point in opposite directions

  • Depth of a node = number of edges from the root down to it. The root has depth 0.
  • Height of a node = number of edges from it down to its deepest leaf. Leaves have height 0.

Click any node. The pink path goes up to the root (depth). The orange path goes down to the farthest leaf (height).

Now press Label all depths, then Label all heights. Depths count up as you go down the tree; heights count up as you go up the tree. They're mirror images, and they're computed in opposite directions.

Who has the information?

Ask: to know this number for node X, whose information do I need?

  • Depth of X depends only on X's ancestors (how many there are). X's parent knows its own depth, so it can tell X: "you're one deeper than me." → pass it down as a parameter.
  • Height of X depends only on X's descendants. Nobody above X knows anything about X's subtree. X has to ask its children and wait. → get it back as a return value.
Rule of thumb: if a node's answer depends on what's above it, pass it down through a parameter (top-down). If it depends on what's below it, bring it up through the return value (bottom-up). 
def label_depth(node, depth):
    if node is None:
        return
    node.depth = depth                  # known immediately, on arrival
    label_depth(node.left, depth + 1)   # hand it down
    label_depth(node.right, depth + 1)

label_depth(root, 0)

def height(node):
    if node is None:
        return -1
    left_h = height(node.left)      # must wait for children…
    right_h = height(node.right)
    return 1 + max(left_h, right_h) # …known only on the way back

Watch when the numbers appear

Switch between the two problems below and press ▶ Play on each. Don't look at the values, look at the timing:

  • Depth: a node's badge appears the moment it's called, before any of its children are visited. The numbers go down with the calls.
  • Height: a node's badge appears only when it returns, after both children have answered. The numbers come back up with the returns. The root is the last to know.

Also look at the call stack for depth: each frame carries depth in its signature, e.g. label_depth(D, 2). The information travels in the arguments. For height, the frames carry left_h and right_h: the information comes back in return values.

"Maximum depth" is the height of the root

This one causes real confusion, because LeetCode 104 is called "Maximum Depth of Binary Tree" and the standard solution is the height function.

It's not a contradiction: the deepest node's depth equals the root's height (both are the length of the longest root-to-leaf path). You can compute that number either way:

def max_depth(node):
    if node is None:
        return 0                    # nodes convention, like LeetCode
    return 1 + max(max_depth(node.left), max_depth(node.right))

def max_depth(root):
    best = 0
    def visit(node, depth):
        nonlocal best
        if node is None:
            return
        best = max(best, depth)     # depth known on the way down
        visit(node.left, depth + 1)
        visit(node.right, depth + 1)
    visit(root, 1)                  # nodes convention: root is depth 1
    return best

Both are O(n) and both are correct. The bottom-up one is shorter because the question "how tall is the tree below me?" is naturally a bottom-up question. The top-down one needs a shared best variable because no single call knows the final answer.

Side by side

Depth Height
Measures edges up to the root edges down to the deepest leaf
Root 0 the tree's height
Leaves vary 0
Depends on ancestors descendants
Recursion direction top-down bottom-up
Information travels in parameters return values
Known at the call (pre-order) the return (post-order)
Base case does nothing / stops returns -1 (or 0)

Check yourself

Two siblings always have the same ___. (depth or height?)

Depth: they have the same parent, so the same ancestors. Their heights can be completely different.

A node's height changes if you add a node somewhere. Where?

Only if the new node is in its subtree (below it). A node's depth changes only if something changes above it.

You need 'for every node, the sum of values on the path from the root to it'. Top-down or bottom-up?

Top-down: it depends on ancestors. Pass running_sum + node.val down as a parameter.

You need 'for every node, the number of nodes in its subtree'. Top-down or bottom-up?

Bottom-up: it depends on descendants. Return 1 + L + R.