Diameter of Tree

How It Works

The diameter is the longest path between any two nodes, counted in edges, and the longest path in the whole tree must pass through some node as its highest point. At that node, the path length equals the left subtree's height plus the right subtree's height. So a single post-order traversal computes each node's height, and at every node it checks leftHeight + rightHeight against a global maximum. The function returns 1 + max(leftHeight, rightHeight) so the parent can continue the same computation.

This piggybacks the diameter check onto the height calculation, visiting each node once for O(n) time and O(h) stack space. The naive alternative — computing height separately at every node — repeats work on shared subtrees and degrades to O(n^2) on skewed trees. The same skeleton generalizes to longest univalue path and similar problems where the answer arches over a node.

Step-by-Step Visualization

Code

static int diameter;

static int diameterOfBinaryTree(TreeNode root) {
  diameter = 0;
  height(root);
  return diameter;
}

static int height(TreeNode node) {
  if (node == null) return 0;
  int left = height(node.left);
  int right = height(node.right);
  diameter = Math.max(diameter, left + right);
  return 1 + Math.max(left, right);
}

// Tree:     1
//          / //         2   3   → diameter = 3 (path: 4→2→1→3)
//        / //       4   5

Tips & Gotchas

Practice Problems

• 1Diameter of Binary Tree
• 2Longest Univalue Path
• 3Binary Tree Maximum Path Sum
• 4Diameter of N-Ary Tree

About the Path Problems Pattern

Find paths in a tree that optimize some value (max sum, min length, specific target). Paths can go root-to-leaf, or through any nodes. The key insight: at each node, the best path either goes through it or doesn't.

Common Trees Interview Problems

• Maximum Depth of Binary Tree
• Validate BST
• Binary Tree Level Order Traversal
• Lowest Common Ancestor
• Serialize and Deserialize Binary Tree
• Diameter of Binary Tree

Frequently Asked Questions

Other Path Problems Techniques