Calculating Tree Metrics
You'll learn how to write recursive algorithms that measure important properties of binary trees like height, node counts, and balance factors.
The Core Idea
Think of a tree metric as a measurement that describes some property of your tree structure. Just as you might measure a physical tree's height from ground to tallest branch, we measure binary tree properties by breaking the problem into smaller subproblems — the essence of recursion. Each metric follows a pattern: compute the metric for left and right subtrees, then combine those results to get the parent's metric.
Common Tree Metrics
Height Calculation
The height of a tree is the longest path from root to any leaf. Recursively: the height of a node is 1 + max(left_height, right_height). A null node has height -1 (or 0, depending on convention).
Node Count
The total node count is straightforward: count yourself (1), plus all nodes in your left subtree, plus all nodes in your right subtree. Base case: a null node contributes 0.
Balance Factor
The balance factor of a node measures how balanced its subtrees are: height(left) - height(right). A balanced tree keeps this value between -1 and 1 for every node. This metric combines two calculations: you need the height of both subtrees to compute balance.
The Recursive Pattern
All these metrics follow the same template:
- Base case: What's the value for an empty tree?
- Recursive step: Calculate metric for left and right subtrees
- Combine: Merge the subresults using addition, max, subtraction, etc.
This pattern makes tree algorithms elegant but requires understanding that each recursive call operates on progressively smaller subtrees until hitting base cases.
Key Takeaway: Tree metrics are computed recursively by solving for subtrees first, then combining results—height uses max, count uses sum, and balance uses subtraction of heights.