Diameter of Binary Tree

Problem

Return the diameter of a binary tree — the longest path (in edges) between any two nodes. The path may or may not pass through the root.

Constraints

• 1 ≤ nodes ≤ 10⁴

Approach — Tree Traversal

This is a Tree Traversal problem. The idea: traverse the tree — DFS recursively, or BFS level by level — and combine the results from each subtree. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time.

Solution code

Python

class Solution:
    def diameterOfBinaryTree(self, root):
        best = 0
        def depth(node):
            nonlocal best
            if not node:
                return 0
            l = depth(node.left)
            r = depth(node.right)
            best = max(best, l + r)
            return 1 + max(l, r)
        depth(root)
        return best

Java

class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        int[] best = {0};
        depth(root, best);
        return best[0];
    }
    private int depth(TreeNode n, int[] best) {
        if (n == null) return 0;
        int l = depth(n.left, best), r = depth(n.right, best);
        best[0] = Math.max(best[0], l + r);
        return 1 + Math.max(l, r);
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.