Computing the Height of a Binary Tree
Most tree recursion prints things on the way down. Height computation is the first one where the answer flows back up: each call waits for both children to report, combines their results, and returns something to its own parent. Watching those return values propagate is what turns tree recursion from a memorised pattern into something you can reason about.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
struct Node {
int val;
Node* left;
Node* right;
};
Node* make(int v) {
Node* n = new Node();
n->val = v; n->left = NULL; n->right = NULL;
return n;
}
int height(Node* r) {
if (r == NULL) return -1;
int lh = height(r->left);
int rh = height(r->right);
return 1 + (lh > rh ? lh : rh);
}
int main() {
Node* root = make(1);
root->left = make(2); root->right = make(3);
root->left->left = make(4);
root->left->left->left = make(5);
cout << height(root) << endl;
return 0;
}Returns -1 for an empty tree so height counts edges; this tree has height 3, along the path 1 to 2 to 4 to 5.
How it works, step by step
Each node asks its children first
The two recursive calls run to completion before the return statement executes. A node cannot know its height until both subtrees have reported theirs, which is why nothing is computed on the way down.
The answer is built during the unwind
Leaves return first, then their parents combine and return, and so on up to the root. Stepping through and watching each frame's lh and rh get filled in as its children return is the clearest possible picture of what a return value actually does.
Max, not sum
Height is the longest single path, so you take the larger of the two subtree heights, not their total. Using + instead of max computes the total number of edges in the tree, which is a real quantity but a different one.
The +1 accounts for the edge to the child
Standing at a node, the path down is one edge plus the longest path from the taller child. That single edge is where the +1 comes from, and it is what makes the recursion accumulate depth.
The base case defines the convention
Returning -1 for NULL makes a single leaf have height 0, counting edges. Returning 0 for NULL makes a leaf have height 1, counting nodes. Neither is wrong, but mixing them within one codebase produces answers that are consistently off by one.
Complexity
Every node is visited exactly once and does constant work, so time is linear in node count; the space is the recursion stack, which equals the height — meaning the very degenerate trees whose height you are measuring are also the ones most likely to overflow the stack while measuring it.
Common bugs
Returning 0 for NULL and then reporting edge counts
The two conventions differ by exactly one, and the mismatch propagates silently. A balance check that compares subtree heights still works either way, but any code that turns height into an index, a level number, or an array size will be off by one everywhere. Pick a convention and write it down.
Adding instead of taking the maximum
return 1 + lh + rh counts edges in the whole subtree rather than along the longest path. On a balanced tree it grows linearly with n instead of logarithmically, so the number looks wildly wrong — but on a chain-shaped tree it is accidentally correct, which is exactly the test case people try first.
Calling height inside a balance check at every node
The naive isBalanced computes height(node->left) and height(node->right) at every node, recomputing the same subtree heights repeatedly for O(n squared) total work. The fix is a single postorder pass that returns height and propagates a failure sentinel. On a deep tree the difference is dramatic and easy to observe in a step count.
Stack overflow while measuring a degenerate tree
A tree of 200,000 nodes inserted in sorted order is a chain, and the recursion needs 200,000 frames. The function that tells you the tree is unbalanced crashes because the tree is unbalanced. An explicit stack or a level-order count avoids it.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
What is the difference between height and depth of a tree?
Height is measured upward from a node to its deepest descendant; depth is measured downward from the root to that node. The root has depth 0 and the maximum height; a leaf has height 0 and its depth equals its level. The height of the tree is the height of the root.
Why does the height function return -1 for an empty tree?
Because that convention counts edges rather than nodes, which makes a single-node tree have height 0. With the +1 in the return, a leaf's two null children both report -1 and the leaf correctly reports 0. Returning 0 for NULL is the node-counting convention and shifts every answer by one.
How do you compute the height of a binary tree?
Recursively: the height of a node is one plus the greater of its two subtree heights, with an empty subtree returning -1. Each node waits for both children to return before computing its own value, so the answer is assembled bottom-up during the recursion's unwind. It runs in O(n) time.
Can you compute tree height without recursion?
Yes, with a level-order traversal: process the tree one level at a time using a queue and count how many levels you complete. This uses O(w) space where w is the widest level, which is safer than recursion on very deep trees where the call stack would overflow.