Diameter of Binary Tree Easy 0 attempts
LeetCode ↗

Diameter of Binary Tree

Easy TreeBinary TreeDFS LeetCode

For a binary tree, the diameter is the length — counted in edges — of the longest path connecting any two of its nodes; this path may or may not pass through the root. Return that length.

Input Format
Implement diameterOfBinaryTree(root). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

Input
root = [1]
Output
0
Constraints
  • 1 <= number of nodes <= 10^4
  • -100 <= Node.val <= 100
Test Cases (2)
Case 1
Args: [[1,2,3,4,5]] Expected: 3
Case 2
Args: [[1]] Expected: 0
Topics
TreeBinary TreeDFS

Iterative Postorder

Collect a parent-before-child order and process it backward. Each node contributes the sum of its two child heights to the diameter.

javascript
function diameterOfBinaryTree(root) {
  if (!root) return 0;
  const order = [], stack = [root];
  while(stack.length) {
    const node=stack.pop();order.push(node);
    if(node.left)stack.push(node.left);
    if(node.right)stack.push(node.right);
  }
  const heights = new Map();let diameter=0;
  for(let i=order.length-1;i>=0;i--) {
    const node=order[i],l=heights.get(node.left)||0,r=heights.get(node.right)||0;
    diameter=Math.max(diameter,l+r);heights.set(node,1+Math.max(l,r));
  }
  return diameter;
}

Time: O(n) | Space: O(n) auxiliary space, excluding output

Saved in this browser only. Private to you.

JavaScript