The O(n) Club: The Binary Tree Diameter Problem (Now With 100% Less Root Worship)

The O(n) Club: The Binary Tree Diameter Problem (Now With 100% Less Root Worship)

⚡ TL;DR

For anyone too caffeinated to read: the “diameter” of a binary tree is the maximum number of edges you can walk between any two nodes—no, the root is not the algorithmic king here. Stop recalculating heights, use DFS, win back O(n) runtime, impress your rubber duck.

// Brute force: for dramatic effect ONLY
int diameter(TreeNode root) {
    if (root == null) return 0;
    int left = height(root.left);
    int right = height(root.right);
    int rootDiameter = left + right;
    return Math.max(rootDiameter,
        Math.max(diameter(root.left), diameter(root.right)));
}
int height(TreeNode node) {
    if (node == null) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
}

🧠 How Devs Usually Mess This Up

Ah, classic mistakes:

🔍 What’s Actually Going On

Think of each tree node as a traffic circle. The diameter is the longest stretch of asphalt you could drive—across any two points, even if that journey stays entirely within the leftmost suburb. For each stop (node), your longest potential joyride through that junction is left road height + right road height. Keep score globally! No node favoritism.

The good news: a post-order DFS gives you subtree heights as you bubble up. When you’re done, your global maxDiameter is the record for “how long can I go without a U-turn?”

🛠️ PseudoCode

• Start DFS from root (or trunk, or wherever your journey begins).
• At each node, get left and right subtree heights via recursion.

  int left = dfs(node.left);
  int right = dfs(node.right);

• Update maxDiameter if left + right is greater than what you’ve clung to so far.
• Return the height of this subtree: 1 + Math.max(left, right)
• Once DFS says “done,” your globally updated maxDiameter is the answer.

💻 The Code

// DFS that won't let your interviewer down
class Solution {
    int maxDiameter = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return maxDiameter;
    }
    private int dfs(TreeNode node) {
        if (node == null) return 0;
        int left = dfs(node.left);
        int right = dfs(node.right);
        maxDiameter = Math.max(maxDiameter, left + right);
        return 1 + Math.max(left, right);
    }
}
// TreeNode definition for those allergic to copy-pasting
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Node vs. Edge confusion: Paths have one fewer edge than nodes. It’s not a fence, it’s a chain-link.
• Root tunnel vision: The hardest journey can loop deep in a leg. Root is not your center of the universe (for once).
• Runtime gotchas: The smart DFS is O(n) time (one visit per node) and O(h) space (stack), so your laptop’s fan can finally chill.
• Rogue re-calculation: Please, don’t calculate height inside a loop. Interviewers can sense fear—and O(n²) code.

🧠 Interviewer Brain-Tattoo

“If you’re counting nodes and not edges, you might also think JavaScript is Java. Don’t be that dev. Count edges, keep cool, recurse once.”