Diameter of Binary Tree

EasyTree Binary Tree DFS

An office network is wired as a tree: a core switch sits at the top, and every switch feeds at most two switches below it. The worst-case delay between two machines depends on the network's diameter: the number of cable hops (edges) on the longest path between any two switches.

Given the root of the binary tree that describes the network, return its diameter. The longest path may or may not pass through the root, and it never visits a switch twice. A network with zero or one switch has diameter 0.

Example 1

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

Explanation: The path 4 → 2 → 1 → 3 → 5 → 7 uses 5 cables.

Example 2

Input: root = [10,20,null,30,40]
Output: 2

Explanation: The path 30 → 20 → 40 has 2 hops, and so does 30 → 20 → 10.

Example 3

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

Explanation: The longest path, 5 → 3 → 2 → 4 → 6, never reaches the root.

Constraints

The tree has at most 10^4 nodes.
Node values are integers from -100 to 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