The O(n) Club: Longest Univalue Path: When Trees, Edges, and Your Patience All Snap

The O(n) Club: Longest Univalue Path — When Trees, Edges, and Your Patience All Snap

⚡ TL;DR

Find the longest path—counted in edges, not nodes!—where all binary tree nodes wear the same value. Spoiler: Most folks count wrong and hand their interviewer a headache. Here’s the brute-force flavor (Java):

// Brute force (please don’t):
int maxPath = 0;
// For each node, run DFS for every possible path!
// Guaranteed O(n^2) coffee consumption.

🧠 How Devs Usually Mess This Up

Some developers believe in counting every single node like they’re at a census bureau. But this problem cares about edges—so a chain with 3 nodes is just 2 edges. Bonus error: assuming the path must cozy up to the root, when really, the best run could be in some rogue left or right subtree nobody invited.

🔍 What’s Actually Going On

Think of your binary tree as a series of gossipy neighbors: information only flows down a line if you both share the same weird hobby (aka value). At each house (node), you peek left and right—if neighbors match, you add them to your growing rumor chain (edge count). To catch the longest one, use DFS from every node and always track a global “best so far”, because sometimes your root is just not that popular.

🛠️ PseudoCode

• Create a global max variable to hold the top univalue path.
• Recursive dfs(node):
  • If node is null, return 0. The recursion fairy ends here.
  • Check left and right: dfs(node.left), dfs(node.right).
  • If child matches the same value, add 1 to the corresponding path.
  • Don’t combine left+right for return—just update global max with both. Return max of left or right to parent call.

💻 The Code

// Java definition for a binary tree node.
class TreeNode {
  int val;
  TreeNode left, right;
  TreeNode(int x) { val = x; }
}
 class Solution {
  int maxLen = 0;
  public int longestUnivaluePath(TreeNode root) {
    dfs(root);
    return maxLen;
  }
  
  private int dfs(TreeNode node) {
    if (node == null) return 0;
    int left = dfs(node.left);
    int right = dfs(node.right);
    int leftPath = 0, rightPath = 0;
    if (node.left != null && node.left.val == node.val) {
      leftPath = left + 1;
    }
    if (node.right != null && node.right.val == node.val) {
      rightPath = right + 1;
    }
    maxLen = Math.max(maxLen, leftPath + rightPath);
    return Math.max(leftPath, rightPath);
  }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Edges, not nodes: Yes, really. Write it in marker on your hand. Three nodes = two edges. Don’t let interviewer smugness win.
• Path doesn’t always involve the root, your favorite child may be hiding mid-tree.
• Never zig and zag: Add left and right paths only for global max update, but return just one direction per recursion.
• Empty tree? Zero. Single node? Also zero. Not a trick question.
• Time and space? O(n), nothing fancy. Your recursion stack simply visits everyone once, like a polite DFS robot.

🧠 Interviewer Brain-Tattoo

“If you want to see a candidate squirm, ask them to count edges instead of nodes. But if you want to see pure joy, show them how tidy DFS makes recursion with global state management.”