Lesson 7 · Advanced structures and algorithms

Tree Diameter and Height

The diameter of a tree is the maximum distance between any two leaves, which often does not pass through the root node.

Diameter Is Not Height

The diameter of a tree is the number of edges on the longest path between any two nodes in it. The height of a node is the number of edges on the longest downward path from that node to a leaf. They are different quantities, and conflating them is the error the whole problem is built around.

A height is measured downward from one node. A diameter is measured between two nodes, and the path connecting them bends: it runs up from one node to some common ancestor, then back down to the other. The topmost node on that path is the only one where the path changes direction.

The consequence that catches people out is that the diameter need not pass through the root. A tree whose root has one shallow child and one deep child may have its longest path buried entirely inside that deep subtree, never touching the root at all. Any solution that only considers the root's two subtree heights is wrong on exactly these trees — and right on the balanced ones people test with.

The reframing that makes the problem tractable: for each node, ask what the longest path through that specific node would be, treating it as the turning point. The diameter is then the maximum of that quantity over all nodes. This converts a global question about pairs into a local question asked n times.

Note also that the two endpoints of the longest path are always leaves. If an endpoint had a child, extending to that child would give a longer path, contradicting maximality — a small observation that becomes the basis of the two-pass method described later.

Height goes down from one node; diameter runs between two
The longest path bends at exactly one node — its highest point
It need not touch the root
Ask, for every node, the longest path turning at it

The Formula at Each Node

With the reframing in place, the local calculation is short. For a node with left subtree height L and right subtree height R, the longest path turning at that node descends as far as possible on each side.

That gives L + R + 2 edges: L edges down the left, R edges down the right, plus the two edges joining the node to its children. Using the convention that a leaf has height 0 and a null child has height −1 makes this formula work without special cases — a leaf computes −1 + −1 + 2 = 0, correctly reporting that no path bends at a leaf.

The height convention is where implementations diverge, so it is worth fixing one deliberately. If instead a null child has height 0 and a leaf has height 1, the through-path becomes L + R and the returned height becomes 1 + max(L, R). Both are correct; mixing them is what produces answers off by one or two, and stating which you use is the difference between a clean exam answer and a suspicious one.

Each node must therefore produce two different values, and separating them is the crux of the algorithm. Upward to its parent it returns its height — 1 + max(L, R) — because a parent can only continue a path down one side. Sideways into a global record it contributes its through-path, L + R + 2, which cannot be passed upward because a bent path cannot be extended by an ancestor.

That asymmetry is the whole insight. Returning the through-path instead of the height is the standard bug: it allows a parent to build a path that goes down, back up, and down again, which is not a path in a tree.

The two values each node produces, under the leaf-height-0 convention
Value	Formula	Goes where
Height	`1 + max(L, R)`	Returned to the parent
Path turning here	`L + R + 2`	Compared against the running best
Null child	height `−1`	Makes the leaf case work with no branch

Through-path at a node is L + R + 2 edges
Height returned upward is 1 + max(L, R)
Never return the through-path — a bent path cannot be extended
Null height −1 removes the leaf special case

One Post-Order Pass

The traversal must be post-order: a node cannot compute anything until both subtree heights are known, so both children must be fully processed before the node itself is handled. Attempting this pre-order does not work, since the required values do not exist yet.

The global maximum is held outside the recursion — a field, a closure variable, or a single-element array, depending on the language. Each node updates it with best = max(best, L + R + 2) and then returns its height. The recursion carries the height; the mutable variable accumulates the answer.

This is what makes it O(n): every node is visited exactly once and does O(1) work. The naive alternative — for each node, call a separate height function on both subtrees — recomputes the same heights repeatedly and costs O(n²), degrading to that on skewed trees where it matters most. The efficient version differs only in computing the height and the diameter in the same pass rather than in two.

Space is O(h) for the call stack, so O(log n) on a balanced tree and O(n) on a degenerate one — worth stating, since a skewed tree of a million nodes will overflow the stack in a recursive implementation and needs an iterative post-order traversal instead.

For a general (n-ary) tree the same method applies with one change: instead of a left and a right height, take the two largest child heights and sum them. Everything else — post-order, return the height, record the through-path — is identical.

Post-order is required: children must finish before the parent
Keep the best-so-far outside the recursion
O(n) time; recomputing heights per node would be O(n²)
O(h) stack space — a degenerate tree needs an iterative traversal

Key reference

Terms, operations, and practical uses

Definitions

Tree DiameterThe length of the longest path between any two nodes in a tree. It does not necessarily pass through the root.
Node HeightThe maximum number of edges on a path from the node down to a leaf.
Path LengthUsually defined by the number of edges between nodes, though sometimes defined by the number of nodes.

Recursive Approach

Post-order AggregationAt each node, compute the height of the left and right subtrees first.
Local Path ComputationThe longest path passing through a specific node is exactly left_height + right_height.
Global StateMaintain a global maximum variable that is updated if the current node's local path exceeds the known maximum diameter.

Graph Approach

First BFSStart a Breadth-First Search from any arbitrary node to find the furthest possible node, which we'll call Node A.
Second BFSStart a second BFS from Node A. The furthest node from A is Node B. The path from A to B is the diameter.
ApplicabilityThis two-BFS method works on any unrooted tree (acyclic graph) and avoids deep recursion stacks.

Implementation

Measure the longest path in a tree

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

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

root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6), TreeNode(7)))
print('Diameter:', Solution().diameterOfBinaryTree(root), 'edges')

#include <iostream>
#include <algorithm>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x, TreeNode* l = nullptr, TreeNode* r = nullptr) : val(x), left(l), right(r) {
    }
};
class Solution {
    int dia = 0;
    int height(TreeNode* node) {
        if (!node) return 0;
        int l = height(node->left);
        int r = height(node->right);
        dia = max(dia, l + r);
        return 1 + max(l, r);
    }
    public:
    int diameterOfBinaryTree(TreeNode* root) {
        height(root);
        return dia;
    }
};
int main() {
    TreeNode* root = new TreeNode(1,
    new TreeNode(2, new TreeNode(4), new TreeNode(5)),
    new TreeNode(3, new TreeNode(6), new TreeNode(7)));
    cout << "Diameter: " << Solution().diameterOfBinaryTree(root) << " edges\n";
}

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int x) {
            val = x;
        }
        TreeNode(int x, TreeNode l, TreeNode r) {
            val = x;
            left = l;
            right = r;
        }
    }
    int dia = 0;
    int height(TreeNode node) {
        if (node == null) return 0;
        int l = height(node.left);
        int r = height(node.right);
        dia = Math.max(dia, l + r);
        return 1 + Math.max(l, r);
    }
    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return dia;
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1,
        new TreeNode(2, new TreeNode(4), new TreeNode(5)),
        new TreeNode(3, new TreeNode(6), new TreeNode(7)));
        System.out.println("Diameter: " + new Main().diameterOfBinaryTree(root) + " edges");
    }
}

Watch it run

Step through it

Running on seven-node tree, root 1

Output

Read all 11 Steps

Goal The diameter is the longest path between any two nodes. It need not pass through the root.
Post-order Compute each node's height, and at every node check the path that bends through it.
Descend left Recurse to 2, then to leaf 4.
Leaf 4 A leaf has height 0 and returns immediately.
Leaf 5 The sibling leaf also returns height 0.
Bend at 2 Node 2 sees left height 0 and right height 0. A path through it spans 0 + 0 + 2 = 2 edges. Record best = 2.
Height of 2 2 returns height 1 — one more than its tallest child.
Right side The same walk happens under 3, over leaves 6 and 7.
Bend at 3 Node 3 also spans 0 + 0 + 2 = 2 edges. best stays 2. 3 returns height 1.
Bend at the root The root sees left height 1 and right height 1: a path of 1 + 1 + 2 = 4 edges. best becomes 4.
Diameter The longest path runs 4 → 2 → 1 → 3 → 6: four edges. Every node was visited once, so this is O(n).

Edges or Nodes, and the Two-Pass Method

The single most common source of a wrong answer is the counting convention. The diameter can be measured in edges or in nodes, and the two differ by exactly one: a path visiting 5 nodes traverses 4 edges.

Most textbook definitions and most competitive-programming problems use edges. Some interview problems ask for nodes. The formulas above count edges; add one for the node count. Read the problem statement for which it wants — a single-node tree has diameter 0 in edges and 1 in nodes, and that case alone will tell you which convention a judge expects.

Two boundary cases deserve explicit handling. An empty tree has diameter 0 by convention, and the recursion should return the null height without touching the global. A single node has diameter 0 in edges, which the formula produces correctly as −1 + −1 + 2.

There is a second, quite different algorithm worth knowing for unweighted trees given as graphs. Run a BFS or DFS from any vertex and find the farthest vertex u; then run a second traversal from u and find the farthest vertex v. The distance from u to v is the diameter — two passes, O(n) each.

The reason it works rests on the earlier observation that both endpoints of a longest path are leaves: the farthest vertex from any starting point is provably an endpoint of some diameter. This method is often more convenient for a tree stored as an adjacency list rather than as parent-child nodes, and it does not require the tree to be rooted at all. It relies on there being no cycles and no weights — on a general graph it gives no such guarantee.

Edges and nodes differ by one — read which the problem wants
Empty tree is 0; a single node is 0 edges or 1 node
Two-pass BFS: farthest from anywhere, then farthest from there
That method needs an unweighted tree, not a general graph