Height & diameter
Scenario
To find the longest communication path between any two computers in a network tree, a developer calls `get_height(left) + get_height(right)` at every single node, causing their program to run in painfully slow O(n^2) time.
How do you calculate tree height and global diameter simultaneously in a single O(n) pass?
Why it exists
Problem: Calculating tree height separately at every node to find the maximum diameter results in repetitive subtree traversals taking O(n^2) time.
Naive approach: For every node in the tree, call a helper function `height(node.left)` and `height(node.right)`.
Better idea: Use a bottom-up post-order traversal. Each recursive step returns the node's own height `1 + max(left_h, right_h)` while simultaneously updating a global diameter variable `max_diameter = max(max_diameter, left_h + right_h)`.
Mental model
Return more than you are asked: return subtree height upwards to your parent, while side-effecting global max diameter at your node.
At each node, compute `left_height` and `right_height` from post-order child returns. The longest path passing THROUGH this node is `left_height + right_height` (edges). Update `global_diameter = max(global_diameter, left_height + right_height)`. Then return `1 + max(left_height, right_height)` to the parent so it can compute its own height.
Repeated decision: at this node, combine left and right subtree HEIGHTS -- update the best diameter, then return the node's own height.
Explanation
Definitions:
- Height of a Node: Number of edges on the longest downward path to a leaf (null node height = 0 for node-count framing or -1 for edge-count framing; here we use height as depth level where null = 0).
- Diameter of a Tree: The length of the longest path between ANY two nodes in a tree (measured in number of edges). The path does NOT necessarily have to pass through the root.
- Height Invariant: `height(node) = 1 + max(height(node.left), height(node.right))`
- Diameter-Through-Node Invariant: `diameter_at_node = height(node.left) + height(node.right)`
Why Naive O(n^2) is Bad:
`def diameter(root):`
`if not root: return 0`
`d_root = height(root.left) + height(root.right)`
`return max(d_root, diameter(root.left), diameter(root.right))`
Because `height()` takes O(n) time and is called at every node, total time is O(n^2).
Optimal O(n) Single-Pass Pattern:
Maintain a non-local variable `max_diameter = 0`:
`def get_height(node):`
`if not node: return 0`
`left_h = get_height(node.left)`
`right_h = get_height(node.right)`
`max_diameter = max(max_diameter, left_h + right_h)`
`return 1 + max(left_h, right_h)`
Walkthrough on a Skewed Tree where Diameter Dodges Root:
Tree:
1
/
2
/ \
3 4
/ \
5 6
- At node `3`: `left_h = 1` (leaf 5), `right_h = 0`. Returns `2`. Diameter at 3 = 1.
- At node `4`: `left_h = 0`, `right_h = 1` (leaf 6). Returns `2`. Diameter at 4 = 1.
- At node `2`: `left_h = 2` (sub-tree at 3), `right_h = 2` (sub-tree at 4).
- Diameter through `2` = `left_h + right_h = 2 + 2 = 4` edges (path: 5 -> 3 -> 2 -> 4 -> 6).
- `max_diameter` updated to 4!
- Node `2` returns height `1 + max(2, 2) = 3` to root `1`.
- At root `1`: `left_h = 3`, `right_h = 0`. Diameter through root = 3. `max_diameter` remains 4!
Notice the longest path dodges root `1` completely!
Related Application - Height-Balanced Check:
The same bottom-up post-order return pattern determines if a tree is height-balanced (where subtrees of every node differ in height by at most 1). At each node, compute `left_h` and `right_h`. If `abs(left_h - right_h) > 1` (or if either child returned -1), return -1 to signal imbalance upwards immediately. Otherwise return `1 + max(left_h, right_h)`. This checks balance in O(n) time instead of naive O(n^2).
Key points
- Post-Order Single Pass: Bottom-up traversal processes children first, allowing height return and diameter update in O(n) time.
- Root Independence: Tree diameter does NOT necessarily pass through the root node.
- Return Value vs Global Side-Effect: Function return value feeds parent height calculations; global side-effect records maximum path across all nodes.
Pattern: Single-Pass Post-Order Aggregation
Recognition cues:
- tree diameter / longest path
- height-balanced tree check
- bottom-up return-value with max tracking
Failure signals
- Problem asks for the longest path between any two nodes in a binary tree.
- Problem asks to check if a binary tree is height-balanced.
Engineering examples
Network Latency Bound in Hierarchy
Calculate the worst-case message propagation delay between any two nodes in a hierarchical network.
Network latency is proportional to the tree diameter (the longest hop path between any two terminal nodes).
UI Tree Layout Budgeting
Determine maximum depth rendering bounds for deeply nested UI trees.
Height calculations establish container layout budgets in single-pass tree passes.
When not to use
- Graphs with cycles or non-tree structures: Graph diameter requires all-pairs shortest path algorithms (Floyd-Warshall or BFS from all vertices).
Common mistakes
- Assuming the diameter always passes through the root: In skewed or unbalanced trees, the longest path between two leaves often exists entirely inside a deep left or right subtree.
- Recomputing height at every node (O(n^2) naive trap): Calling a helper `height()` inside a recursive `diameter()` function re-traverses subtrees redundantly, ballooning runtime to O(n^2).
- Confusing edge count vs node count: Edge count diameter = node count on path - 1. Pay close attention to whether the problem asks for number of edges or number of nodes.
Recall questions
- What is the relationship between node height and the heights of its subtrees?
- Does the diameter of a binary tree always pass through the root node?
- Why is computing diameter in a single post-order pass O(n) instead of O(n^2)?
Questions & answers
Diameter of Binary Tree: Given the root of a binary tree, return the length of the diameter of the tree in edges.
Use post-order DFS helper that returns height `1 + max(left, right)` and updates global `max_diameter = max(max_diameter, left + right)`. Return `max_diameter`.
Approach: Single-pass bottom-up post-order DFS with global max tracker.
Balanced Binary Tree: Determine if a binary tree is height-balanced (subtrees of every node differ in height by at most 1).
Use post-order DFS helper returning height. If `abs(left_h - right_h) > 1`, return -1 to signal imbalance upwards early.
Approach: Post-order bottom-up DFS returning -1 on imbalance.
Interesting facts
- The exact same single-pass pattern (returning max branch path while updating global path sum) is used to solve LeetCode Hard 'Binary Tree Maximum Path Sum'.
Continue learning
Previous: Binary tree & traversals
Previous: DFS: pre / in / post
Next: Binary heap
Related: Binary tree & traversals
Related: DFS: pre / in / post
Related: Lowest common ancestor