Tree Height & Depth —
Watch the recursion unwind and count.
Height is computed bottom-up: recursion drops all the way down to the leaves first, then adds 1 at every level as it climbs back up. The answer doesn't exist until the unwind finishes. Watch each recursive call hit a leaf, return 0, and bubble the count upward on LearnBug — the part that's easy to get backwards on paper.
What is Tree Height?
Height is the number of edges on the longest path from a node down to a leaf. A single leaf node has height 0. The height of any node is 1 + max(height(left), height(right)) — you can't know a node's height until you know both of its children's heights first, which is why this is naturally recursive.
Why visualization helps
The recursion has to go all the way down before it can come back up with an answer — there's no useful return value until a call hits None or a leaf. LearnBug highlights the current node on the way down and shows the returned height value on the way back up, so the "dive then add 1 per level" pattern is visible instead of abstract.
Height vs depth — easy to mix up
Height — measured upward from a leaf
Height of a node = longest path down to a leaf. Height of the whole tree = height of the root. A single leaf has height 0.
Depth — measured downward from the root
Depth of a node = number of edges from the root down to that node. The root has depth 0. Depth is naturally computed top-down, height bottom-up.
Why this matters
Tree height caps recursion/call-stack depth for every other traversal on this hub, and is the key input to checking whether a tree is balanced.
height(4) on 4(2(1,3), 6)
height(4) can't return yet — it needs height(2) and height(6) first
The call dives into height(2) before it can compute anything. Nothing has returned so far — this is the dive phase.
height(2) dives into height(1) and height(3) — both are leaves
Nodes 1 and 3 have no children, so height(1) = 0 and height(3) = 0 return immediately. This is the bottom of the dive.
height(2) = 1 + max(0, 0) = 1 — first "add 1 and bubble up" step
With both children's heights known, node 2 computes its own height: one more than the taller child. Now height(6) is still needed.
height(6) = 0 (leaf) — now height(4) can finally compute
Node 6 has no children, so it returns 0. With both height(2)=1 and height(6)=0 known, node 4 computes 1 + max(1, 0) = 2.
Return: height(4) = 2 ✓ longest path (4 → 2 → 1 or 4 → 2 → 3) has 2 edges
Height and max depth
def height(node):
if node is None:
return -1 # empty tree has height -1 (no edges)
return 1 + max(height(node.left), height(node.right))def max_depth(node):
# Some codebases define "leaf has depth 1" instead of "height 0" —
# same recursion, different base case. Always check the convention.
if node is None:
return 0
return 1 + max(max_depth(node.left), max_depth(node.right))Complexity Notes
Frequently asked questions
What's the difference between height and depth?
Height is measured upward from a node to its deepest leaf — computed bottom-up. Depth is measured downward from the root to a node — computed top-down (usually by passing a running depth counter into the recursion instead of relying on the return value).
Why does height(None) return -1 in this code?
Height counts edges, not nodes. A single leaf has no edges below it, so its height is 0 — which the formula 1 + max(...) only produces correctly if an empty subtree contributes -1. Some implementations instead define height in terms of node count and use 0 for empty and 1 for a leaf — just be consistent within one codebase.
How is this used to check if a tree is balanced?
A tree is height-balanced if, at every node, the height of the left subtree and the height of the right subtree differ by no more than 1 — checked recursively the same way height itself is computed. This is exactly the core check inside AVL tree rebalancing logic.
Can I compute height iteratively instead of recursively?
Yes — level order (BFS) traversal naturally gives you height too: count how many full levels you process before the queue empties. It avoids recursion but needs O(w) queue space instead of O(h) call-stack space.
Watch the height value bubble up from the leaves
Paste your height calculation into LearnBug and see each return value climb the call stack.