Diameter of Binary Tree

EASY✓ CHIP-TIMEDLC #543 — FULL STATEMENT ↗

The drill: Find the longest path between any two nodes in a binary tree, measured in edges — that path doesn't have to pass through the root.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A binary tree arrives, and the task is to find the longest path between any two of its nodes, measured by how many edges that path crosses.

This path does not have to pass through the root at all — it might sit entirely within one subtree, well away from the top of the tree, and the drill has to consider every node as a possible peak of the path.

A tree with just a single node has no edges to cross, so its diameter comes out to zero.

EX 01

root = []

→ 0

EMPTY TREE

EX 02

root = [1]

→ 0

SINGLE NODE, NO EDGES

EX 03

root = [1, 2]

→ 1

ONE EDGE

the tree can hold anywhere from zero to a few thousand nodes
node values can be negative, zero, or positive
diameter is measured in edges on the longest node-to-node path, which need not pass through the root

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

At any single node, the longest path passing through it is the height of its left side plus the height of its right side. The catch: the true winner might live entirely inside one subtree, never touching this node at all.

HINT 2 THE STRUCTURE

So check every node as a candidate 'peak' and keep the best left-height + right-height seen anywhere. The naive way just recomputes height from scratch at every node.

HINT 3 ONE STEP FROM THE ANSWER

Fold the two jobs into one pass: a height function that, on its way back up from each node, also updates a running best using the heights it already computed — no recomputation needed.

COACH'S BOARD — THE PATTERN, STEP BY STEP

HEIGHT AND DIAMETER TOGETHERPATTERN · HEIGHT AND DIAMETER TOGETHERroot = [1, 2, 3, 4, 5, 6, 7]

STEP 1

Diameter is the longest edge-path between any two nodes — it need not pass through the root. One post-order pass tracks height and a running best sum together.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/diameter-of-binary-tree.py — RACE PACE

LANG ▸

PACE ▸

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

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

        height(root)
        return best

TIME O(N)SPACE O(H)PYTHON · RACE PACE · 15 LN

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

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

TIME O(N²)SPACE O(H)PYTHON · TRAINING PACE · 15 LN

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 lh = height(node.left);
        int rh = height(node.right);
        best = Math.max(best, lh + rh);
        return 1 + Math.max(lh, rh);
    }
}

TIME O(N)SPACE O(H)JAVA · RACE PACE · 19 LN

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

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

TIME O(N²)SPACE O(H)JAVA · TRAINING PACE · 16 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED