Height

The height of a node is the number of edges on the longest downward path from that node to any leaf in its subtree. The height of the tree is the height of the root. In this course, a leaf has height 0, and an empty child contributes height -1 inside recursive formulas.

That convention makes the recurrence clean. If a node has no children, both child heights are -1, so its height is 1 + max(-1, -1) = 0. Some textbooks count nodes instead of edges, but interviews are safest when you state your convention before using it.

Height is a bottom-up value. A parent cannot know its height until it knows the heights of both children. That is exactly postorder traversal: compute the left subtree, compute the right subtree, then process the node.

For [3,9,20,null,null,15,7], nodes 9, 15, and 7 are leaves with height 0. Node 20 has child heights 0 and 0, so its height is 1. Root 3 has child heights 0 and 1, so the tree height is 2.

The recurrence is: height(node) = 1 + max(height(node.left), height(node.right)). The base value for null is -1 under the leaf-height-zero convention. This base value is not arbitrary; it makes the parent of two empty children become height 0.

Many recursive tree problems reuse this exact shape. Maximum depth, balanced-tree checks, diameter, and several subtree aggregation problems all start by returning information from children to parent.

The first mistake is mixing edge height and node height halfway through the solution. If null returns 0, then a leaf returns 1, which is node-count height. That is also valid if stated clearly, but it changes examples and balance calculations by one.

The second mistake is trying to compute height top-down without stored information. Depth is naturally top-down because it counts from the root. Height is naturally bottom-up because it depends on the deepest leaf below the node.