Skip to main content

17. Diameter of Binary Tree

easyAsked at Notion

Find the longest path between any two nodes in a tree — a metric Notion would use to measure the worst-case traversal depth across a workspace's page hierarchy, tying depth-first search to real document-graph reasoning.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given the root of a binary tree, return the length of the diameter of the tree. The diameter is the length of the longest path between any two nodes, measured in number of edges. The path does not have to pass through the root.

Constraints

  • 1 <= number of nodes <= 10^4
  • -100 <= Node.val <= 100

Examples

Example 1

Input
root = [1,2,3,4,5]
Output
3

Explanation: Longest path: [4,2,1,3] or [5,2,1,3], length 3 edges.

Example 2

Input
root = [1,2]
Output
1

Approaches

1. Naive DFS per node

At each node, compute max height of left and right subtrees separately, sum them as the local diameter, update a global max — but recomputes subtree heights repeatedly.

Time
O(n^2)
Space
O(h)
function diameterOfBinaryTree(root) {
  function height(node) {
    if (!node) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
  }
  function diam(node) {
    if (!node) return 0;
    const throughRoot = height(node.left) + height(node.right);
    return Math.max(throughRoot, diam(node.left), diam(node.right));
  }
  return diam(root);
}

Tradeoff:

2. Single-pass DFS with closure

Compute height bottom-up in one DFS; at each node update a shared max with left-height + right-height — O(n) by combining the two metrics in one traversal.

Time
O(n)
Space
O(h)
function diameterOfBinaryTree(root) {
  let maxDiam = 0;
  function height(node) {
    if (!node) return 0;
    const left = height(node.left);
    const right = height(node.right);
    maxDiam = Math.max(maxDiam, left + right);
    return 1 + Math.max(left, right);
  }
  height(root);
  return maxDiam;
}

Tradeoff:

Notion-specific tips

Notion asks this to verify you can recognize the 'compute two things in one pass' pattern — tracking both the return value (height) and a side-effect (global max) simultaneously. Mention the workspace graph analogy to show product awareness.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Diameter of Binary Tree and other Notion interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →