Diameter of Binary Tree

easy tree dfs

Problem

Given the root of a binary tree, return the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Inputtree = 1,2,3,4,5,null,null (level order)

Output3

DFS returns each subtree's height; at each node, candidate diameter = leftHeight + rightHeight.

tree (level order, 'null' for missing; use small trees)

def diameter_of_binary_tree(root):
    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

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

class Solution {
    int best = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return best;
    }
    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);
    }
}

int best = 0;
int height(TreeNode* node) {
    if (!node) return 0;
    int lh = height(node->left);
    int rh = height(node->right);
    best = max(best, lh + rh);
    return 1 + max(lh, rh);
}
int diameterOfBinaryTree(TreeNode* root) {
    best = 0;
    height(root);
    return best;
}

Explanation

The diameter is the longest path (in edges) between any two nodes, and that path may not even pass through the root. Checking every pair of nodes would be slow, so we want something smarter.

The key idea: any longest path has a single highest point where it bends. At that top node, the path goes down its left side as far as possible and down its right side as far as possible. So the best path through a node is simply leftHeight + rightHeight.

We run one post-order DFS where height(node) returns how tall the subtree is. While computing that, we also update a shared best with best = max(best, lh + rh) — testing this node as the bending point.

The function returns 1 + max(lh, rh) to its parent, because a parent can only continue down one side of this child. The path-through value and the returned height are two different things, which is the subtle part.

Example: 1,2,3,4,5. The bending point is the root 1: its left height is 2 (down through 2 to 4 or 5) and its right height is 1 (down to 3), so leftHeight + rightHeight = 2 + 1 = 3. The matching path 4 → 2 → 1 → 3 spans 3 edges, so the answer is 3. Note this lh + rh sum is larger at the root than at node 2, where lh + rh = 1 + 1 = 2.

Time: O(n) Space: O(h)