☕ DSA Java Articles

Topics › Binary Trees › Medium Problems

Diameter of Binary Tree

Easy TUF ID 130 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given the root of a binary tree, return its diameter: the number of edges on the longest path between any two nodes. The path does not have to pass through the root, and it never visits a node twice. A tree with zero or one node has diameter 0.

Constraints: 0 ≤ n ≤ 10^4 nodes, values fit in an int (the values play no role).

Example 1

tree (level order) = [1, 2, 3, 4, 5]

       1
      / \
     2   3
    / \
   4   5

answer = 3          // 4 -> 2 -> 1 -> 3 (or 5 -> 2 -> 1 -> 3): three edges

Example 2

tree (level order) = [1, 2, null, 3, 4, 5, null, null, 6, 7, null, null, 8]

          1
         /
        2
       / \
      3   4
     /     \
    5       6
   /         \
  7           8

answer = 6          // 7 -> 5 -> 3 -> 2 -> 4 -> 6 -> 8; the root is not on it

The key structural fact: every path in a tree has a unique highest node, the one closest to the root. From there the path goes down into the left subtree, down into the right subtree, or both. If we fix the highest node v, the longest such path goes as deep as possible on each side, so it has height(v.left) + height(v.right) edges, where height counts nodes (an empty subtree has height 0). The diameter is the maximum of that quantity over all nodes v. Example 2 shows why we must consider every node and not only the root: through the root the best is 4 + 0 = 4, but at node 2 it is 3 + 3 = 6.

Approach 1: Brute force

Intuition. Apply the fact directly. For every node, call a separate height function on its two children, add the results, and keep the maximum. It is correct, but each height call walks a whole subtree, and nodes deep in the tree get measured once for every ancestor.

Algorithm.

  1. If the node is null, return 0.
  2. through = height(left) + height(right), the longest path whose highest node is this one.
  3. Return the maximum of through, the answer for the left subtree and the answer for the right subtree.
static int height(TreeNode node) {
    if (node == null) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
}

static int bruteForce(TreeNode root) {
    if (root == null) return 0;
    int through = height(root.left) + height(root.right);
    return Math.max(through, Math.max(bruteForce(root.left), bruteForce(root.right)));
}

Complexity. Time O(n^2) in the worst case. On a chain of n nodes the height calls cost n + (n - 1) + ... + 1. On a balanced tree it is O(n log n). Space O(h) for the recursion.

Approach 2: Optimal, one post-order pass

Intuition. The brute force computes the same heights over and over. But a post-order traversal already produces every node’s height exactly once, bottom-up: a node’s height is 1 + max(lh, rh) where lh and rh are the heights its children just returned. At that very moment we also hold lh + rh, the longest path bending at this node. So we compute the height for the parent and, as a side effect, update a running maximum of lh + rh. One traversal yields both.

The function therefore has two outputs: the return value is the height, which is what the parent needs to extend a path upward, and the side channel best[0] is the diameter candidate, which uses both sides and so cannot be extended by the parent. Keeping these two quantities apart is the heart of this problem and of Maximum path sum. A one-element array is used for the running maximum because Java passes primitives by value; a field or a small holder object works too.

Algorithm.

  1. Set best = 0.
  2. heightAndDiameter(null) = 0.
  3. For a node: get lh and rh from the children, set best = max(best, lh + rh), return 1 + max(lh, rh).
  4. Return best after the call on the root.
static int optimal(TreeNode root) {
    int[] best = new int[1];
    heightAndDiameter(root, best);
    return best[0];
}

static int heightAndDiameter(TreeNode node, int[] best) {
    if (node == null) return 0;
    int lh = heightAndDiameter(node.left, best);
    int rh = heightAndDiameter(node.right, best);
    best[0] = Math.max(best[0], lh + rh);      // longest path that bends at this node
    return 1 + Math.max(lh, rh);               // what this node offers to its parent
}

Dry run on Example 1:

node lh rh best after returns
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 answer is best = 3.

Complexity. Time O(n): each node is visited once with constant work. Space O(h) for the recursion: O(log n) for a balanced tree and O(n) for a skewed one.

Why it is correct. By the structural fact above, the diameter equals the maximum of height(v.left) + height(v.right) over all nodes v. The traversal visits every node, and when it does, lh and rh are exactly those two heights, so the maximum it records is exactly the diameter.

Edges versus nodes

The LeetCode and TUF versions count edges, which is why a node with two leaf children gives 1 + 1 = 2. Some older GeeksforGeeks versions count nodes on the path; in that convention the answer is lh + rh + 1. Read the examples before coding: in Example 1 the edge count is 3 and the node count would be 4. Mixing the conventions shifts every answer by one, and the empty tree case changes too.

Edge cases and pitfalls