Skip to main content

7. Diameter of Binary Tree

easyAsked at Redis

Find the longest path between any two nodes; Redis uses it to gauge post-order recursion which mirrors how the engine walks command call trees.

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

Problem

Given the root of a binary tree, return the length of the diameter (the number of edges on the longest path between any two nodes). The path may or may not pass through the root.

Constraints

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

Examples

Example 1

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

Example 2

Input
root = [1,2]
Output
1

Approaches

1. Recompute depth per node

For each node compute left and right depth from scratch.

Time
O(n^2)
Space
O(h)
function depth(n) { return n ? 1 + Math.max(depth(n.left), depth(n.right)) : 0; }
function walk(n) {
  if (!n) return 0;
  best = Math.max(best, depth(n.left) + depth(n.right));
  walk(n.left); walk(n.right);
}

Tradeoff:

2. Single post-order with diameter accumulator

Return depth from each subtree while updating a closure-scoped best diameter.

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

Tradeoff:

Redis-specific tips

Redis interviewers reward post-order recursion done in one pass; mention how Redis' MULTI/EXEC stack is also walked once for atomicity and that you respect linear-time guarantees.

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 Redis interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →