Algorithms / Tree Height Balance
Least You Need to Know: Tree Height, Balance, and Diameter Intuition
Bottom-up tree questions ask each subtree to return a small summary such as its height, whether it is balanced, or the best path seen so far. The key interview move is to decide what summary the parent needs from each child.
The least you need to know
- A subtree answer is often computed from child summaries and then returned upward.
- Height is naturally a bottom-up quantity because a node's height depends on its children's heights.
- Balanced-tree checks compare the heights of the left and right subtrees at every node.
- A tree diameter may pass through the current node as left height plus right height, but the best diameter may also live entirely inside one subtree.
- Sometimes the cleanest recursive helper returns more than one value, such as height plus a validity flag.
Key notation
height(v)
length of the longest downward path from node v
diameter
length of the longest path between any two tree nodes
balanced
every node has child heights differing by at most one
Tiny worked example
- To compute whether a binary tree is balanced, first ask each child subtree for its height.
- At the parent, compare the left and right heights.
- The parent is locally balanced when the difference is at most one and both child subtrees were balanced.
- That is a classic example of returning a small summary upward from each recursive call.
Common mistakes
- Students often recompute subtree heights many times instead of returning them once from the recursion.
- Students often think the diameter must pass through the root, but the longest path can sit entirely inside one subtree.
- Students often choose a helper return value that is too small to answer the parent's question cleanly.
How to recognize this kind of problem
- The prompt asks for height, balance, depth, longest path, or a subtree summary.
- The parent decision clearly depends on answers already computed for the children.
- A postorder traversal fits better than preorder because child answers are needed first.
Next recommended lesson
Continue through this topic with Least You Need to Know: Tree Traversals and Recursive Calls.
Least You Need to Know: Tree Traversals and Recursive CallsRelated lessons
Keep going with nearby lessons in the same topic.