Diameter of Binary Tree
Last Updated: March 29, 2026
Understanding the Problem
We need to find the longest path between any two nodes in a binary tree, measured in edges (not nodes). The tricky part is that this path doesn't have to go through the root.
Picture the tree from 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. That path has 3 edges and happens to be the longest. But in other trees, the longest path might live entirely within one subtree, never touching the root at all.
The key observation is this: at every node in the tree, there's a potential "diameter path" that goes down into the left subtree, passes through that node, and goes down into the right subtree. The length of that path equals the height of the left subtree plus the height of the right subtree (both measured in edges). The answer to the problem is the maximum of this value across all nodes.
So the problem reduces to: for every node, compute left height + right height, and track the global maximum. That's very similar to computing heights bottom-up, which is a well-known tree DFS pattern.
Key Constraints:
Number of nodes in [1, 10^4]→ With n up to 10,000, an O(n) solution is ideal. Even O(n^2) would give 10^8 operations, which is borderline. We should aim for O(n).-100 <= Node.val <= 100→ Node values are irrelevant. We only care about the tree's structure.At least 1 node→ We don't need to handle the empty tree case.
Approach 1: Brute Force (DFS at Every Node)
Intuition
The most straightforward way to think about this: the diameter through any given node equals the height of its left subtree plus the height of its right subtree (both measured in edges). So if we compute the height of the left and right subtrees at every node, and track the maximum sum, we have our answer.
We already know how to compute the height of a subtree -- it's a simple recursive function. So the brute force approach just calls that height function from every node in the tree. At each node, compute height(left) + height(right), keep track of the max, and that's the diameter.
The problem? Computing the height from every node means we're doing a lot of redundant work. The height of a deeply nested subtree gets recomputed every time an ancestor asks for it.
Algorithm
- Write a
height(node)helper that returns the height of a subtree in edges. - Traverse every node in the tree using DFS.
- At each node, compute
height(node.left) + height(node.right). - 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(n). The recursion stack depth equals the height of the tree, which is O(n) in the worst case (skewed tree).
This approach works but recomputes heights redundantly. What if we computed the height of each node exactly once and calculated the diameter at the same time, during a single bottom-up traversal?
Approach 2: Bottom-Up DFS (Optimal)
Intuition
Here's the key insight. We're already computing heights recursively, and the diameter through any node is just leftHeight + rightHeight. So instead of computing heights separately and then visiting each node again, we combine both operations into a single DFS.
We do a post-order traversal where each recursive call returns the height of that subtree. But as a side effect, at every node, we also compute leftHeight + rightHeight and update a global maximum. By the time the traversal finishes, the global maximum holds the answer.
Think of it this way: in the brute force, we visit every node and ask "how tall are your subtrees?" -- which requires re-traversing those subtrees. In the optimal approach, the subtrees tell their parent how tall they are on the way back up. No re-traversal needed.
The diameter of a binary tree must pass through some node as its "highest point." At that node, the path goes down into the left subtree and down into the right subtree. The length of this path equals the height of the left subtree plus the height of the right subtree (both measured in edges from that node).
Since we don't know which node is the highest point of the diameter, we check every node. The bottom-up DFS is perfect for this because it computes heights from the leaves upward. By the time we process a node, we already have the exact heights of both children. We compute leftHeight + rightHeight, compare it to our running maximum, and pass the height upward. Every node is visited exactly once.
Algorithm
- Initialize a variable
maxDiameterto 0. - Define a helper function
dfs(node)that returns the height of the subtree rooted atnode(measured in edges). - 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 diameter through this node). - Return
1 + max(leftHeight, rightHeight)as the height of this subtree. - 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).