Diameter of Binary Tree

time: O(n)
space: O(h)
tags: trees · recursion · dfs

in the wild Maximum hop count across a star/tree-shaped network; longest kinematic span across a robot's URDF (joint-to-joint farthest pair).

Problem

Given the root of a binary tree, return its diameter — the length of the longest path between any two nodes. Length is measured in edges (so a single node has diameter 0). The path need not go through the root.

Examples

        1
       / \             diameter = 3
      2   3            (path 4 → 2 → 1 → 3 or 5 → 2 → 1 → 3)
     / \
    4   5

        1              diameter = 1
         \             (path 1 → 2)
          2

      (single node)    diameter = 0

Why this is the canonical "two-values-per-recursion" problem

A first attempt: "for each node, the longest path through it = depth(left) + depth(right). Take the max over all nodes." That's correct! But the obvious code recomputes depth from every node — O(n²).

The win: piggyback both answers onto one recursion. At every node, return its height, and as a side-effect update the global best (height(left) + height(right)). One pass, O(n).

This "compute one thing per node, but also bubble up a different thing through the return value" pattern is the second tree pattern you must master after max-depth's plain recursion. The same trick solves:

Is this BST balanced? — return height; track failure as a side-effect.
Largest BST subtree? — return (size, min, max, is-bst); track largest as side-effect.
Sum of all paths from leaves? — return prefix-sum; track total.

Hints

Hint 1 — what "passes through" a node means

Any path in the tree has a highest node (the one closest to the root). The path goes down some prefix of the left subtree and some prefix of the right subtree from that node. Its length in edges is therefore (depth of left subtree) + (depth of right subtree).

Hint 2 — avoid the O(n²) trap

If you call a separate depth() helper from each recursive step, you re-walk the subtree under every node — O(n²) total. Instead, have the helper return the depth so the caller never re-walks.

Hint 3 — side-effect into a closed-over variable

Your recursive helper returns the height (for its parent's use). Inside, before returning, it updates a shared best counter with left_h + right_h. After the full traversal, best is the diameter.

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

Solution

from dataclasses import dataclass
from typing import Optional

@dataclass
class Node:
    val: int
    left:  Optional["Node"] = None
    right: Optional["Node"] = None

def diameter(root: Optional[Node]) -> int:
    best = 0
    def height(n: Optional[Node]) -> int:
        nonlocal best
        if n is None:
            return 0
        lh = height(n.left)
        rh = height(n.right)
        best = max(best, lh + rh)         # path *through* n is lh + rh edges
        return 1 + max(lh, rh)            # height returned to parent
    height(root)
    return best

# Build the example trees.
t1 = Node(1, Node(2, Node(4), Node(5)), Node(3))
t2 = Node(1, None, Node(2))
t3 = Node(1)
t4 = None
cases = [(t1, 3), (t2, 1), (t3, 0), (t4, 0)]
for root, expected in cases:
    got  = diameter(root)
    mark = "✓" if got == expected else "✗"
    print(f"{mark} diameter(...) = {got}  (expected {expected})")

class Node {
  constructor(val, left = null, right = null) {
    this.val = val; this.left = left; this.right = right;
  }
}

function diameter(root) {
  let best = 0;
  function height(n) {
    if (n === null) return 0;
    const lh = height(n.left);
    const rh = height(n.right);
    best = Math.max(best, lh + rh);
    return 1 + Math.max(lh, rh);
  }
  height(root);
  return best;
}

const t1 = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3));
const t2 = new Node(1, null, new Node(2));
const t3 = new Node(1);
const t4 = null;
const cases = [[t1, 3], [t2, 1], [t3, 0], [t4, 0]];
for (const [root, expected] of cases) {
  const got = diameter(root);
  console.log(`${got === expected ? "✓" : "✗"} diameter(...) = ${got}  (expected ${expected})`);
}

pub struct Node {
    pub val:   i32,
    pub left:  Option<Box<Node>>,
    pub right: Option<Box<Node>>,
}

pub fn diameter(root: &Option<Box<Node>>) -> i32 {
    // Helper returns the height; mutates best on the way up.
    fn height(n: &Option<Box<Node>>, best: &mut i32) -> i32 {
        let Some(n) = n else { return 0; };
        let lh = height(&n.left,  best);
        let rh = height(&n.right, best);
        *best = (*best).max(lh + rh);    // path through n
        1 + lh.max(rh)                    // height to parent
    }
    let mut best = 0;
    height(root, &mut best);
    best
}

fn leaf(v: i32) -> Option<Box<Node>> {
    Some(Box::new(Node { val: v, left: None, right: None }))
}
fn node(v: i32, l: Option<Box<Node>>, r: Option<Box<Node>>) -> Option<Box<Node>> {
    Some(Box::new(Node { val: v, left: l, right: r }))
}

fn main() {
    let t1 = node(1, node(2, leaf(4), leaf(5)), leaf(3));
    let t2 = node(1, None, leaf(2));
    let t3 = leaf(1);
    let t4: Option<Box<Node>> = None;
    let cases = [(&t1, 3), (&t2, 1), (&t3, 0), (&t4, 0)];
    for (root, expected) in cases {
        let got  = diameter(root);
        let mark = if got == expected { "✓" } else { "✗" };
        println!("{mark} diameter(...) = {}  (expected {})", got, expected);
    }
}

#include <algorithm>
#include <iostream>

struct Node {
    int   val;
    Node* left;
    Node* right;
    Node(int v, Node* l = nullptr, Node* r = nullptr) : val(v), left(l), right(r) {}
};

int diameter(Node* root) {
    int best = 0;
    // Local lambda so we can capture `best` by reference.
    auto height = [&](auto&& self, Node* n) -> int {
        if (!n) return 0;
        int lh = self(self, n->left);
        int rh = self(self, n->right);
        best   = std::max(best, lh + rh);
        return 1 + std::max(lh, rh);
    };
    height(height, root);
    return best;
}

int main() {
    Node* t1 = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3));
    Node* t2 = new Node(1, nullptr, new Node(2));
    Node* t3 = new Node(1);
    Node* t4 = nullptr;
    std::pair<Node*, int> cases[] = { {t1, 3}, {t2, 1}, {t3, 0}, {t4, 0} };
    for (auto& [root, expected] : cases) {
        int got = diameter(root);
        std::cout << (got == expected ? "✓" : "✗")
                  << " diameter(...) = " << got
                  << "  (expected " << expected << ")\n";
    }
}

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int          val;
    struct Node* left;
    struct Node* right;
} Node;

static int imax(int a, int b) { return a > b ? a : b; }

// Helper returns height, side-effects into *best.
static int height(Node* n, int* best) {
    if (!n) return 0;
    int lh = height(n->left,  best);
    int rh = height(n->right, best);
    if (lh + rh > *best) *best = lh + rh;
    return 1 + imax(lh, rh);
}

int diameter(Node* root) {
    int best = 0;
    height(root, &best);
    return best;
}

static Node* mk(int v, Node* l, Node* r) {
    Node* n = malloc(sizeof(Node));
    n->val = v; n->left = l; n->right = r;
    return n;
}

int main(void) {
    Node* t1 = mk(1, mk(2, mk(4, NULL, NULL), mk(5, NULL, NULL)), mk(3, NULL, NULL));
    Node* t2 = mk(1, NULL, mk(2, NULL, NULL));
    Node* t3 = mk(1, NULL, NULL);
    Node* t4 = NULL;
    printf("%s diameter(t1) = %d  (expected 3)\n", diameter(t1) == 3 ? "✓" : "✗", diameter(t1));
    printf("%s diameter(t2) = %d  (expected 1)\n", diameter(t2) == 1 ? "✓" : "✗", diameter(t2));
    printf("%s diameter(t3) = %d  (expected 0)\n", diameter(t3) == 0 ? "✓" : "✗", diameter(t3));
    printf("%s diameter(t4) = %d  (expected 0)\n", diameter(t4) == 0 ? "✓" : "✗", diameter(t4));
    return 0;
}

idle

The Rust version is the most explicit about the pattern — the helper has two outputs: the height (return value, for the parent) and the running best (&mut parameter, for the side-effect). All five implementations are isomorphic.

Complexity

Time: O(n) — single post-order pass; each node does O(1) work.
Space: O(h) recursion stack, where h is the tree height.
Naïve (don't do this): Separately computing depth() from every node visited by an outer traversal is O(n²). On a 1M-node tree that's a million-fold slowdown.

In the wild

Network diameter. Across a tree-shaped peer-to-peer overlay, the diameter is the worst-case hop count between any two peers.
Robot kinematic span. The longest "joint-to-joint" path in a robot's URDF — useful for collision-bounding-volume estimation and self-collision pruning.
Phylogenetic trees. Maximum evolutionary distance between any two species in a clade.
Compiler register-pressure heuristics. The deepest expression-tree path informs how many temporaries the back end may need.

Variations

Diameter weighted by edge cost. Same recursion, but accumulate weighted height. Now you need long-double or i64 for accumulation.
Diameter of a general tree (not just binary). Recurse over all children; track the top two heights, not just left/right. Returned height is 1 + top1.
Diameter of an unrooted tree. Run BFS from any node to find a farthest node u; BFS from u finds a farthest v; dist(u, v) is the diameter. Two passes, O(n).
Balanced check. Return (height, balanced); same shape, different side-effect.