40. Diameter of Binary Tree

EasyTree Binary Tree DFS

Given the root of a binary tree, return its diameter: the number of edges on the longest path between any two nodes.

The path does not have to go through the root, and it never visits a node twice. A tree with zero or one node has diameter 0.

Example 1

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

Explanation: The path 4 → 2 → 1 → 3 (or 5 → 2 → 1 → 3) has 3 edges.

Example 2

Input: root = [1,2]
Output: 1

Example 3

Input: root = [1,2,null,3,4,5,null,null,6,7,null,null,8]
Output: 6

Explanation: The longest path is 7 → 5 → 3 → 2 → 4 → 6 → 8. It stays inside the left subtree and never touches the root.

Constraints

The number of nodes is in the range [0, 10^4]
-100 <= Node.val <= 100

💡 Hint 1

Every path has a single highest node. If the path peaks at node x, how long can it be?

💡 Hint 2

A path peaking at x has length height(x.left) + height(x.right), counting heights in nodes. Compute heights bottom-up and track the best sum seen.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Run a post-order DFS that returns each node's height (nodes on the longest downward path, 0 for null). At each node, the longest path that peaks there uses both arms, so it has leftHeight + rightHeight edges. Update a running maximum with that sum, then return 1 + max(leftHeight, rightHeight) to the parent. One pass computes every height and every candidate diameter.

Time O(n)Space O(h), where h is the tree height

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

class Solution {
    private int best = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return best;
    }

    private int height(TreeNode node) {
        if (node == null) return 0;
        int l = height(node.left), r = height(node.right);
        best = Math.max(best, l + r);
        return 1 + Math.max(l, r);
    }
}

/**
 * Definition for a binary tree node (provided):
 * function TreeNode(val, left, right) { this.val = val ?? 0; this.left = left ?? null; this.right = right ?? null; }
 *
 * @param {TreeNode} root
 * @return {number}
 */
function diameterOfBinaryTree(root) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit