Diameter of Binary Tree

DFS returning depth, tracks max as side effect

Key insight: the answer might not pass through the root. Track a global max.

Published Apr 16, 2026

Problem

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

Input

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

Output

Explanation

Longest path: 4 → 2 → 1 → 3 (or 5 → 2 → 1 → 3) has 3 edges.

Input

root = [1, 2]

Output

Intuition

The longest path in a binary tree must "elbow" at some node — it goes down one subtree, hits the elbow, and comes back down the other subtree. So the answer is:

diameter = max over all nodes of (depth(left) + depth(right))

If we already know how to compute depth at every node (problem #104), the temptation is to call depth once per node — that gives O(n²) because each depth call walks a subtree.

The fix: compute depths bottom-up, and at each node, use the two child depths you just computed to update the global diameter, then return the depth to your parent. One pass, two outputs per node.

Approach

DFS, depth + side-effect max

TimeO(n)

SpaceO(h)

Recommended

A single helper returns depth. Inside the helper, after recursing into both children, update a closure-captured max_diameter with left_depth + right_depth (in edges). Return 1 + max(left_depth, right_depth) so the parent gets a usable depth.

The two outputs per node are the secret. Splitting them — return depth to parent, write diameter to a shared cell — keeps each call O(1) work.

use std::cell::RefCell;
use std::rc::Rc;

impl Solution {
    pub fn diameter_of_binary_tree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        fn depth(node: Option<Rc<RefCell<TreeNode>>>, best: &mut i32) -> i32 {
            match node {
                None => 0,
                Some(n) => {
                    let nb = n.borrow();
                    let l = depth(nb.left.clone(), best);
                    let r = depth(nb.right.clone(), best);
                    *best = (*best).max(l + r);
                    1 + l.max(r)
                }
            }
        }
        let mut best = 0;
        depth(root, &mut best);
        best
    }
}

Rust · runnable

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val ?? 0;
    this.left = left ?? null;
    this.right = right ?? null;
  }
}

function diameterOfBinaryTree(root: TreeNode | null): number {
  let best = 0;
  const depth = (node: TreeNode | null): number => {
    if (node === null) return 0;
    const l = depth(node.left);
    const r = depth(node.right);
    best = Math.max(best, l + r);
    return 1 + Math.max(l, r);
  };
  depth(root);
  return best;
}

TypeScript · runnable

Pure recursion returning (depth, diameter)

TimeO(n)

SpaceO(h)

Avoid the mutable capture by returning a tuple. The tuple version is pedagogically cleaner because it reveals the "two outputs per node" structure explicitly — you can see the data flow without hunting for a mutated variable.

In production, the side-effect version is shorter and identical asymptotically. Use the tuple version when the calling site needs both numbers.

use std::cell::RefCell;
use std::rc::Rc;

impl Solution {
    pub fn diameter_of_binary_tree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        fn dfs(node: Option<Rc<RefCell<TreeNode>>>) -> (i32, i32) {
            match node {
                None => (0, 0),
                Some(n) => {
                    let nb = n.borrow();
                    let (ld, ldi) = dfs(nb.left.clone());
                    let (rd, rdi) = dfs(nb.right.clone());
                    let here = ld + rd;
                    (1 + ld.max(rd), here.max(ldi).max(rdi))
                }
            }
        }
        dfs(root).1
    }
}

Rust · runnable

function diameterOfBinaryTree(root: TreeNode | null): number {
  const dfs = (node: TreeNode | null): [number, number] => {
    if (node === null) return [0, 0];
    const [ld, ldi] = dfs(node.left);
    const [rd, rdi] = dfs(node.right);
    return [1 + Math.max(ld, rd), Math.max(ld + rd, ldi, rdi)];
  };
  return dfs(root)[1];
}

TypeScript · runnable

Trace

DFS on root = [1, 2, 3, 4, 5]:

node	depth(left)	depth(right)	best after	returns depth
4	0	0	0	1
5	0	0	0	1
2	1	1	2	2
3	0	0	2	1
1	2	1	3	3

The diameter 3 is realized at node 1 (path 4 → 2 → 1 → 3). Note the answer is in edges, not nodes — that's why depth 2 + 1 = 3 is the diameter at the root.

Edge cases

Empty tree — diameter 0.
Single node — no edges, diameter 0.
Linear tree (linked-list shaped) — diameter equals depth − 1.
Diameter not through root — handled because we update best at every node, not just the root.

Takeaway

When a recursive call needs to return one thing to its parent but contribute another to a global answer, split the responsibilities. This pattern recurs everywhere: max path sum (#124) returns single-side path but tracks any-elbow; balanced-tree-check returns depth or sentinel; longest univalue path returns same-color depth. The shape is identical — only the per-node update changes.

Easy#104

Maximum Depth of Binary Tree

1 + max(left_depth, right_depth). This IS the recursive template.

Hard#124

Binary Tree Maximum Path Sum

Like diameter but with values. Return one-side max to parent, track global two-side max.

Easy#226

Invert Binary Tree

The simplest recursive tree transformation. Swap left and right, recurse.