The O(n) Club: Maximum Difference Between Node and Ancestor: Not Your Parent’s Binary Tree Drama

The O(n) Club: Maximum Difference Between Node and Ancestor

⚡ TL;DR

If you want the maximum absolute difference between a node and any ancestor in a binary tree, don’t brute force it—that’s O(N²) and you don’t deserve that. Use DFS instead: pass the high score (max) and low score (min) on each downward path, and let recursion keep the receipts.

// Java: Minimalist DFS, loads of style
public int maxAncestorDiff(TreeNode root) {
    return dfs(root, root.val, root.val);
}
 private int dfs(TreeNode node, int min, int max) {
    if (node == null) return max - min;
    min = Math.min(min, node.val);
    max = Math.max(max, node.val);
    int left = dfs(node.left, min, max);
    int right = dfs(node.right, min, max);
    return Math.max(left, right);
}

🧠 How Devs Usually Mess This Up

You know the type. Some folks try to save every ancestor value, building lists like it’s Stack Overflow badge day. Others treat it as a BST problem (hello, interview tunnel vision) or only compare parent/child. Result: O(N²) solutions, java.util.Collection abuse, and more null checks than actual answers. Let’s retire that maneuver, please.

🔍 What’s Actually Going On

Here’s your mental image: you and your min/max detectors take a stroll from root to leaves. Along any path, the wildest swings happen between the biggest and smallest values you pass—not between every awkward uncle-node and rebellious teenager-node. Just track min and max down the path, compare at the bottom, and never look back. Easy, breezy, no ancestor charts required.

🛠️ PseudoCode

• Create your recursive helper: It gets passed the current node, minimum, and maximum seen so far.

  private int dfs(TreeNode node, int min, int max)

• Base case: If node is null, return max – min because you’ve finished this existential tree branch.

  if (node == null) return max - min;

• Update running min/max: Update min and max with node.val because ancestors can’t hide from extremes.

  min = Math.min(min, node.val);
  max = Math.max(max, node.val);

• Recursive drama: Explore both .left and .right, see who’s got bigger difference.

  int left = dfs(node.left, min, max);
  int right = dfs(node.right, min, max);

• Let the winner reign: Return Math.max(left, right); only the most dramatic difference survives.

💻 The Code

// Definition for binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}
 class Solution {
    public int maxAncestorDiff(TreeNode root) {
        if (root == null) return 0;
        return dfs(root, root.val, root.val);
    }
    private int dfs(TreeNode node, int min, int max) {
        if (node == null) return max - min;
        min = Math.min(min, node.val);
        max = Math.max(max, node.val);
        int left = dfs(node.left, min, max);
        int right = dfs(node.right, min, max);
        return Math.max(left, right);
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• This isn’t a BST. The left child could be bigger than the parent. Don’t assume anything—these trees can be a mess.
• The difference you care about is along the entire path, not just between neighbors.
• Don’t try to collect every ancestor. Min and max are all you need. Marie Kondo approves.
• O(N) time, O(H) stack space (H is tree height) — way better than O(N²) or a therapist bill.
• Root is null? Return 0. Tree has just one node? Still 0. Drama needs at least two actors.

🧠 Interviewer Brain-Tattoo

“In trees—and in life—the biggest shock comes from the biggest extremes. Look for min/max, and skip the ancestor baggage.”