Diameter of Binary Tree
Understanding the Problem
We need to find the longest path between any two nodes in a binary tree, measured in edges (not nodes). The path does not have to pass through the root.
In Example 1, the path [4, 2, 1, 3] goes from a leaf in the left subtree, up through the root, and down to a leaf in the right subtree. It has 3 edges and is the longest in that tree. In other trees, the longest path can live entirely within one subtree and never touch the root.
Every path in a tree has a unique highest node where it bends: the path descends from that node into its left subtree and into its right subtree. Define the height of a subtree as the number of nodes on its longest downward path (0 for an empty subtree, 1 for a single leaf). The longest path bending at a given node then has height(left) + height(right) edges, because each node on the two downward chains contributes the edge connecting it to its parent.
The problem reduces to: for every node, compute height(left) + height(right), and return the maximum across all nodes.
Key Constraints:
Number of nodes in [1, 10^4]→ An O(n^2) solution is about 10^8 operations at this size, which is borderline. O(n) is the target.-100 <= Node.val <= 100→ Node values are irrelevant. Only the tree's structure matters.At least 1 node→ We don't need to handle the empty tree case.
Approach 1: Brute Force (DFS at Every Node)
Intuition
The diameter through any given node is height(left) + height(right), and height is a standard recursive computation. The brute force applies this directly: traverse the tree, call the height helper on both children of each node, and track the maximum sum.
The cost is redundant work. The height of a deep subtree gets recomputed once for every ancestor that asks for it.
Algorithm
- Write a
height(node)helper that returns the number of nodes on the longest downward path fromnode(0 whennodeis null, 1 for a leaf). - Traverse every node in the tree using DFS.
- At each node, compute
height(node.left) + height(node.right), the length in edges of the longest path bending at this node. - Track the maximum value seen across all nodes.
- Return the maximum.
Example Walkthrough
Code
- Time Complexity: O(n log n) for balanced trees, O(n^2) for skewed trees. At each node, we call
height(), which traverses the entire subtree below it. For a balanced tree, this sums to O(n log n). For a skewed tree, it sums to O(n^2). - Space Complexity: O(h), where h is the height of the tree, for the recursion stack (O(n) worst case for a skewed tree). Both the traversal and the height helper recurse at most h levels deep.
The next approach removes the redundancy by computing each height exactly once and tracking the diameter during the same traversal.
Approach 2: Bottom-Up DFS (Optimal)
Intuition
Approach 1 already computes heights recursively, and the diameter through a node is leftHeight + rightHeight. The two computations can share a single post-order DFS: each recursive call returns the height of its subtree, and before returning, it updates a global maximum with leftHeight + rightHeight. When the traversal finishes, the global maximum holds the answer.
In the brute force, a parent re-traverses both subtrees to learn their heights. In the post-order version, the heights arrive as return values from the two recursive calls, so each node does O(1) work beyond visiting its children once.
The diameter path bends at a unique highest node, and at that node its length is exactly the leftHeight + rightHeight the DFS computes there. Since the DFS evaluates this quantity at every node, the diameter is among the candidates. The maximum also never overshoots: leftHeight + rightHeight at any node is the length of a real path in the tree, so no candidate exceeds the diameter. The maximum over all nodes is therefore exactly the diameter.
Algorithm
- Initialize a variable
maxDiameterto 0. - Define a helper function
dfs(node)that returns the height of the subtree rooted atnode, counted in nodes (0 for null, 1 for a leaf). - Base case: if
nodeis null, return 0. - Recursively compute the height of the left subtree:
leftHeight = dfs(node.left). - Recursively compute the height of the right subtree:
rightHeight = dfs(node.right). - Update
maxDiameterwithleftHeight + rightHeight, the length in edges of the longest path bending at this node. - Return
1 + max(leftHeight, rightHeight)as this subtree's height. - After the DFS completes, return
maxDiameter.
Example Walkthrough
Code
- Time Complexity: O(n). Each of the n nodes is visited exactly once during the post-order traversal. At each node, we perform O(1) work.
- Space Complexity: O(h), where h is the height of the tree. The space comes from the recursion stack. For a balanced tree, h = O(log n). For a skewed tree, h = O(n).