#543 Diameter of Binary Tree

Easysolve on LeetCode ↗

frequently reported atMeta Amazon Oracle Bloomberg Google Flipkart

the problem

In plain words

Return the number of edges on the longest path between any two nodes. The path does not have to pass through the root.

in root = [1,2,3,4,5]

out 3

4 → 2 → 1 → 3 (or 5 → 2 → 1 → 3).

in root = [1,2]

out 1

1 ≤ number of nodes ≤ 10⁴
-100 ≤ Node.val ≤ 100

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTree DFS (bottom-up)

Every path has one highest node where it bends. Bending at node X, its length is height(left) + height(right). So compute heights once, bottom-up, and check the bend at every node on the way.

solutions

From brute force to optimal

For each node, compute both subtree heights with separate calls; take the best over all nodes.

diameter(node) = max(h(left) + h(right), diameter(left), diameter(right)).
h() walks the whole subtree each time.

timeO(n²) worst

On a skewed tree each node re-walks everything below it: n + (n−1) + … (O(n log n) if balanced).

spaceO(h)

Recursion stack.

javajava.util.*

1class Solution {2    public int diameterOfBinaryTree(TreeNode root) {3        if (root == null) return 0;4        int throughRoot = height(root.left) + height(root.right);   // longest path bending at root5        int inLeft = diameterOfBinaryTree(root.left);6        int inRight = diameterOfBinaryTree(root.right);7        return Math.max(throughRoot, Math.max(inLeft, inRight));8    }9 10    private int height(TreeNode node) {   // recomputed again and again → slow11        if (node == null) return 0;12        return 1 + Math.max(height(node.left), height(node.right));13    }14}

height(node) returns the height up to the parent and, on the way, updates best = max(best, left + right).

height(null) = 0.
left = height(left), right = height(right).
best = max(best, left + right).
Return 1 + max(left, right).

timeO(n)

Each node is visited once with O(1) work.

spaceO(h)

Recursion stack.

javajava.util.*

1class Solution {2    private int best;3 4    public int diameterOfBinaryTree(TreeNode root) {5        best = 0;6        height(root);7        return best;8    }9 10    /** Returns the height (in nodes) and updates the best path seen so far. */11    private int height(TreeNode node) {12        if (node == null) return 0;13        int left = height(node.left);14        int right = height(node.right);15        best = Math.max(best, left + right);           // path that bends here, in edges16        return 1 + Math.max(left, right);              // what my parent needs17    }18}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    private int best;3 4    public int diameterOfBinaryTree(TreeNode root) {5        best = 0;6        height(root);7        return best;8    }9 10    /** Returns the height (in nodes) and updates the best path seen so far. */11    private int height(TreeNode node) {12        if (node == null) return 0;13        int left = height(node.left);14        int right = height(node.right);15        best = Math.max(best, left + right);           // path that bends here, in edges16        return 1 + Math.max(left, right);              // what my parent needs17    }18}

in the room

How to say it in the interview

talk track

Say the key fact first: "the answer bends at some node; at that node it's left height + right height".
Explain the two different things: what we return (height, for the parent) vs what we record (best bend, for the answer).

traps

Only checking the bend at the root (fails when the longest path lives inside one subtree).
Counting nodes instead of edges — the answer is in edges.

what they ask next

Follow-ups

Longest path with equal values (LC 687)?

Same skeleton: return the longest same-value arm, record left arm + right arm when values match.

before you submit

Edge cases to test

One node → 0.
The longest path can avoid the root entirely.
A chain of n nodes → n − 1 edges.

practise next