Diameter of Binary Tree

Easy Problem 67 of 151 Java and Python

Problem

Given the root of a binary tree, return the length of its diameter: the number of edges on the longest path between any two nodes. The path may or may not pass through the root.

Example 1

Input: root = [1, 2, 3, 4, 5]
Output: 3
Why: The path 4 → 2 → 1 → 3 (or 5 → 2 → 1 → 3) has 3 edges.

Example 2

Input: root = [1, 2]
Output: 1

Constraints

1 ≤ number of nodes ≤ 10⁴

Explanation

Every path has a highest node. Through that node, the longest path goes down the deepest branch on the left and the deepest on the right: height(left) + height(right) edges.

So compute heights bottom-up, and at each node also update a global best with left + right. One traversal does both.

Approach 1 · Naive

Height from every node

Time O(n²) worst case
Space O(h)

For each node, call a separate height function on both children and combine. Heights get recomputed many times.

diameter(node) = max(height(left) + height(right), diameter(left), diameter(right)).
height is computed from scratch each time.

Java

class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int through = height(root.left) + height(root.right);
        return Math.max(through, Math.max(diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right)));
    }

    private int height(TreeNode node) {
        return node == null ? 0 : 1 + Math.max(height(node.left), height(node.right));
    }
}

Python

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        def height(node):
            return 0 if not node else 1 + max(height(node.left), height(node.right))

        if not root:
            return 0
        through = height(root.left) + height(root.right)
        return max(through, self.diameterOfBinaryTree(root.left), self.diameterOfBinaryTree(root.right))

Approach 2 · Optimal

One DFS returning heights

Time O(n)
Space O(h)

A DFS returns each node's height and, on the way, records the best left + right.

dfs(node): return 0 for null.
Get left = dfs(node.left), right = dfs(node.right); update best = max(best, left + right).
Return 1 + max(left, right).

Java

class Solution {
    private int best = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        best = 0;
        height(root);
        return best;
    }

    private int height(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = height(node.left);
        int right = height(node.right);
        best = Math.max(best, left + right);
        return 1 + Math.max(left, right);
    }
}

Python

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        best = 0

        def height(node):
            nonlocal best
            if not node:
                return 0
            left, right = height(node.left), height(node.right)
            best = max(best, left + right)
            return 1 + max(left, right)

        height(root)
        return best

Complexity compared

Approach	Time	Space
Naive Height from every node	O(n²) worst case	O(h)
Optimal One DFS returning heights	O(n)	O(h)

Key takeaways

"Return one thing, record another" is the pattern behind Binary Tree Maximum Path Sum and Balanced Binary Tree.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem