Diameter of Binary Tree

Description

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is defined as the length of the longest path between any two nodes in the tree. This path may or may not pass through the root node.

The length of a path between two nodes is measured by the number of edges between them, not the number of nodes.

For example, in a tree with a single node, the diameter is 0 (there are no edges). In a tree with a root and one child, the diameter is 1 (one edge connects them).

Examples

Example 1

Input: root = [1, 2, 3, 4, 5]

The tree looks like:

Output: 3

Explanation: The longest path is [4, 2, 1, 3] or equivalently [5, 2, 1, 3]. Both paths have 3 edges: 4→2, 2→1, 1→3. Notice this path passes through the root node 1. The diameter is 3.

Example 2

Input: root = [1, 2]

The tree looks like:

    1
   /
  2

Output: 1

Explanation: The only path in this tree is between nodes 1 and 2, which has 1 edge. So the diameter is 1.

Example 3

Input: root = [1, 2, 3, 4, 5, null, null, null, null, 6, 7, null, 8]

The tree looks like:

Output: 5

Explanation: The longest path is [4, 2, 5, 7, 8] with 4 edges, or [3, 1, 2, 5, 7, 8] with 5 edges. The diameter is 5. Importantly, this longest path does NOT pass through the root — it goes from node 3 down to node 8 via the root. This shows why we cannot just compute left height + right height at the root.

Constraints

The number of nodes in the tree is in the range [1, 10^4]
-100 ≤ Node.val ≤ 100

Editorial

Brute Force

Intuition

The diameter passes through some node in the tree. For any node, the longest path that passes through that node is the sum of:

The height of its left subtree (the longest downward path going left)
The height of its right subtree (the longest downward path going right)

This is because the longest path through a node goes as deep as possible into the left subtree and as deep as possible into the right subtree.

The brute force idea is straightforward: visit every node in the tree, compute the height of its left and right subtrees separately, add them together to get the diameter through that node, and keep track of the maximum.

Think of it like measuring rope paths in a family tree. At each person (node), you measure the longest chain of descendants going left and the longest going right. The total rope length through that person is left chain + right chain. The diameter is the longest rope across all people.

The problem with this approach is that computing the height of a subtree requires its own traversal. So for each of the n nodes, we traverse its subtree to compute height — resulting in redundant work. At the root, we traverse the entire tree. At the root's children, we traverse their subtrees again. This overlapping traversal leads to O(n²) time on skewed trees.

Step-by-Step Explanation

Let's trace through with the tree from Example 1: root = [1, 2, 3, 4, 5].

Step 1: Visit node 1 (root). Compute height of left subtree rooted at 2: height(2) = 2 (path 2→4 or 2→5). Compute height of right subtree rooted at 3: height(3) = 1 (just node 3, no children, but height is 0 since it's a leaf — wait, height of a single node is 0 edges). Actually, height(3) = 0 (leaf). Diameter through node 1 = height(left) + height(right) = 2 + 1 = 3. Wait — let me clarify: height here counts edges. height(4) = 0, height(5) = 0, height(2) = 1 + max(0, 0) = 1. No — that gives us wrong values. Let me recount.

Using edges: height of a leaf = 0. height(4) = 0, height(5) = 0. height(2) = 1 + max(height(4), height(5)) = 1 + max(0, 0) = 1. height(3) = 0 (leaf). Diameter through node 1 = height(left=2) + height(right=3) = 1 + 0? That gives 1, not 3.

Actually, we need to be precise. height(node) returns the number of edges from node to its deepest leaf. For computing diameter through a node, we need left_height + right_height where left_height = height(node.left) and right_height = height(node.right). But we also add the edges from node to its left child and from node to its right child.

So: diameter through node = (1 + height(left_child)) + (1 + height(right_child)) when both children exist. But actually the standard formulation uses height where height(null) = -1 or height(null) = 0 with nodes counted. Let me use the standard approach: height(null) = 0 (counting nodes), then diameter through node = height(left) + height(right).

With node-counting height: height(null) = 0, height(leaf) = 1, height(4) = 1, height(5) = 1, height(2) = 1 + max(1, 1) = 2, height(3) = 1. Diameter through node 1 = height(1.left) + height(1.right) = 2 + 1 = 3. ✓

Step 1 (corrected): Visit root (node 1). Call height(left child = 2) → this traverses nodes 2, 4, 5, returning 2. Call height(right child = 3) → traverses node 3, returning 1. Diameter through node 1 = 2 + 1 = 3. Update max_diameter = 3.

Step 2: Visit node 2. Call height(4) = 1. Call height(5) = 1. Diameter through node 2 = 1 + 1 = 2. max_diameter stays 3.

Step 3: Visit node 3 (leaf). height(null) = 0 for both children. Diameter through node 3 = 0 + 0 = 0. max_diameter stays 3.

Step 4: Visit node 4 (leaf). Diameter through node 4 = 0 + 0 = 0. max_diameter stays 3.

Step 5: Visit node 5 (leaf). Diameter through node 5 = 0 + 0 = 0. max_diameter stays 3.

Result: max_diameter = 3.

Brute Force — Computing Height at Every Node — Watch how we visit each node and separately compute the height of its left and right subtrees. The redundancy becomes visible when the same subtrees are traversed multiple times.

Algorithm

Initialize max_diameter = 0.
For every node in the tree (via any traversal — preorder, level-order, etc.):
a. Compute left_height = height(node.left) using a separate height function.
b. Compute right_height = height(node.right) using the same height function.
c. Update max_diameter = max(max_diameter, left_height + right_height).
The height(node) function returns 0 if node is null, otherwise 1 + max(height(node.left), height(node.right)).
Return max_diameter.

Code

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int maxDiameter = 0;
        computeDiameter(root, maxDiameter);
        return maxDiameter;
    }
    
    void computeDiameter(TreeNode* node, int& maxDiameter) {
        if (!node) return;
        
        int leftHeight = height(node->left);
        int rightHeight = height(node->right);
        maxDiameter = max(maxDiameter, leftHeight + rightHeight);
        
        computeDiameter(node->left, maxDiameter);
        computeDiameter(node->right, maxDiameter);
    }
    
    int height(TreeNode* node) {
        if (!node) return 0;
        return 1 + max(height(node->left), height(node->right));
    }
};

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.max_diameter = 0
        self._compute_diameter(root)
        return self.max_diameter
    
    def _compute_diameter(self, node):
        if not node:
            return
        
        left_height = self._height(node.left)
        right_height = self._height(node.right)
        self.max_diameter = max(self.max_diameter, left_height + right_height)
        
        self._compute_diameter(node.left)
        self._compute_diameter(node.right)
    
    def _height(self, node):
        if not node:
            return 0
        return 1 + max(self._height(node.left), self._height(node.right))

class Solution {
    private int maxDiameter = 0;
    
    public int diameterOfBinaryTree(TreeNode root) {
        maxDiameter = 0;
        computeDiameter(root);
        return maxDiameter;
    }
    
    private void computeDiameter(TreeNode node) {
        if (node == null) return;
        
        int leftHeight = height(node.left);
        int rightHeight = height(node.right);
        maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
        
        computeDiameter(node.left);
        computeDiameter(node.right);
    }
    
    private int height(TreeNode node) {
        if (node == null) return 0;
        return 1 + Math.max(height(node.left), height(node.right));
    }
}

Complexity Analysis

Time Complexity: O(n²) in the worst case

For each of the n nodes, we call height() which traverses its entire subtree. In a balanced tree, this gives O(n log n) because each level halves the subtree size. But in a skewed tree (essentially a linked list), computing height at the root traverses all n nodes, at the next node traverses n-1, then n-2, etc. Total: n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = O(n²).

Space Complexity: O(n)

The recursion stack can be as deep as n for a skewed tree. For a balanced tree, the stack depth is O(log n).

Why This Approach Is Not Efficient

The brute force computes height() separately for every node, but each height computation traverses the node's entire subtree. When we compute the diameter at the root, we traverse the whole tree for height. Then we move to the root's left child and traverse its subtree for height again — even though we already visited those same nodes during the root's height computation.

The inefficiency is redundant traversals. Heights of subtrees are computed over and over. With n up to 10^4, O(n²) means up to 10^8 operations — risky for time limits.

Key insight: when we recursively compute the height of a node, we are already visiting every node in its subtree. If we could compute the diameter contribution of each node during the height computation itself, we would visit each node exactly once. Instead of two separate recursive processes (one for visiting all nodes, one for computing height), we combine them into a single DFS that computes height and updates the diameter simultaneously.

Optimal Approach - Single DFS Traversal

Intuition

The optimal approach combines height computation and diameter tracking into a single recursive traversal. The key observation is:

While computing the height of any node, we already know the heights of its left and right subtrees — because we just recursively computed them. At that moment, we can immediately calculate the diameter through this node (left_height + right_height) and update our global maximum.

So we write a single function dfs(node) that:

Returns the height of the subtree rooted at node (used by the parent)
As a side effect, updates the global max_diameter

This is a post-order traversal pattern: process left child, process right child, then combine results at the current node. By the time we process a node, both children have already returned their heights, so we have everything we need.

Think of it like a relay race team reporting upward. Each node asks its left and right children: "how tall are you?" The children answer (that's the recursive return). The node then:

Reports to its parent: "I'm 1 + max(left, right) tall"
Whispers to the scorekeeper: "The longest path through me has left + right edges"

Every node gets visited exactly once. No redundant height computations.

Step-by-Step Explanation

Let's trace through with the tree from Example 1: root = [1, 2, 3, 4, 5].

Step 1: Call dfs(1). Before we can compute anything at node 1, we need heights from both children. Recurse left: dfs(2).

Step 2: Call dfs(2). Again, need children's heights. Recurse left: dfs(4).

Step 3: Call dfs(4). Node 4 is a leaf. dfs(4.left) = dfs(null) = 0. dfs(4.right) = dfs(null) = 0. Diameter through node 4 = 0 + 0 = 0. max_diameter stays 0. Return height = 1 + max(0, 0) = 1.

Step 4: Back at dfs(2). Left height = 1 (from node 4). Recurse right: dfs(5).

Step 5: Call dfs(5). Node 5 is a leaf. Left = 0, Right = 0. Diameter through 5 = 0. Return height = 1.

Step 6: Back at dfs(2). Left height = 1, Right height = 1. Diameter through node 2 = 1 + 1 = 2. Update max_diameter = max(0, 2) = 2. Return height = 1 + max(1, 1) = 2.

Step 7: Back at dfs(1). Left height = 2 (from node 2). Recurse right: dfs(3).

Step 8: Call dfs(3). Node 3 is a leaf. Left = 0, Right = 0. Diameter through 3 = 0. Return height = 1.

Step 9: Back at dfs(1). Left height = 2, Right height = 1. Diameter through node 1 = 2 + 1 = 3. Update max_diameter = max(2, 3) = 3. Return height = 1 + max(2, 1) = 3.

Result: max_diameter = 3. Each node was visited exactly once.

Single DFS — Height + Diameter in One Pass — Watch the post-order DFS compute heights bottom-up. At each node, the left and right heights are already known, so the diameter through that node is computed instantly. The global max_diameter updates as we go.

Algorithm

Initialize max_diameter = 0.
Define a recursive function dfs(node) that:
a. If node is null, return 0.
b. Recursively compute left_height = dfs(node.left).
c. Recursively compute right_height = dfs(node.right).
d. Update max_diameter = max(max_diameter, left_height + right_height).
e. Return 1 + max(left_height, right_height) (height of this subtree).
Call dfs(root).
Return max_diameter.

The function serves a dual purpose: it returns the height (for the parent to use) and simultaneously updates the diameter (as a side effect). This eliminates all redundant traversals.

Code

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int maxDiameter = 0;
        dfs(root, maxDiameter);
        return maxDiameter;
    }
    
    int dfs(TreeNode* node, int& maxDiameter) {
        if (!node) return 0;
        
        int leftHeight = dfs(node->left, maxDiameter);
        int rightHeight = dfs(node->right, maxDiameter);
        
        // Update diameter: longest path through this node
        maxDiameter = max(maxDiameter, leftHeight + rightHeight);
        
        // Return height of this subtree
        return 1 + max(leftHeight, rightHeight);
    }
};

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.max_diameter = 0
        
        def dfs(node):
            if not node:
                return 0
            
            left_height = dfs(node.left)
            right_height = dfs(node.right)
            
            # Update diameter: longest path through this node
            self.max_diameter = max(self.max_diameter, left_height + right_height)
            
            # Return height of this subtree
            return 1 + max(left_height, right_height)
        
        dfs(root)
        return self.max_diameter

class Solution {
    private int maxDiameter = 0;
    
    public int diameterOfBinaryTree(TreeNode root) {
        maxDiameter = 0;
        dfs(root);
        return maxDiameter;
    }
    
    private int dfs(TreeNode node) {
        if (node == null) return 0;
        
        int leftHeight = dfs(node.left);
        int rightHeight = dfs(node.right);
        
        // Update diameter: longest path through this node
        maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
        
        // Return height of this subtree
        return 1 + Math.max(leftHeight, rightHeight);
    }
}

Complexity Analysis

Time Complexity: O(n)

We visit each of the n nodes exactly once during the DFS traversal. At each node, we perform O(1) work: a comparison, an addition, and a max operation. Total: n × O(1) = O(n). This is a dramatic improvement over the brute force's O(n²) for skewed trees.

Space Complexity: O(h) where h is the height of the tree

The space is dominated by the recursion stack. In the worst case (completely skewed tree), h = n, giving O(n) space. For a balanced tree, h = log n, giving O(log n) space. No additional data structures are used beyond the recursion stack and a single integer for max_diameter.

EASY

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

MEDIUM

HARD

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Diameter of Binary Tree

Description

Examples

Example 1

Example 2

Example 3

Constraints

Editorial

Brute Force

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Single DFS Traversal

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis