The O(n) Club: All the Binary Tree Paths Your Leaves Will Ever Need

The O(n) Club: All the Binary Tree Paths Your Leaves Will Ever Need

⚡ TL;DR

You want every root-to-leaf path in a binary tree? Great! DFS is your ride—recursively or iteratively. Tack each node’s value on a string as you go, but don’t leave stray arrows lying around. Here’s a Java sample to get you 80% there (the remaining 20% is emotional support):

// Java DFS for all paths
void findPaths(TreeNode node, String path, List
<string> res) {
    if (node == null) return;
    if (node.left == null && node.right == null) {
        res.add(path + node.val);
        return;
    }
    findPaths(node.left, path + node.val + "->", res);
    findPaths(node.right, path + node.val + "->", res);
}</string>

🧠 How Devs Usually Mess This Up

Nobody likes to admit it, but everyone’s botched this one at 2am:

• Mislabeled leaves: If there’s even one child, it’s not a true leaf. Don’t promote a twig to foliage.
• String ‘arrow’ carnage: Trailing, leading, doubled, the dreaded “->->”: don’t do it. Paths should look like “1->2->5” not like someone spilled shift keys everywhere.
• Null root faceplant: If root is null and you try to DFS anyway, say hi to Mr. StackOverflow (the error, not the website… unless you like bugging site mods).
• Forgotten state resets: Sharing a mutable StringBuilder between recursion calls is a fast track to spiritual confusion and extra arrows.

🔍 What’s Actually Going On

Visualize your tree like a badly designed dungeon. You’re crawling from the main entrance (root) toward every dead end (leaf), tracing the exact halls you take. DFS is your trustiest lantern: for every passage you enter, scribble the node’s number down. When you see there are no left or right passages left (true leaf), jot down the full route, then backtrack like a dungeon speedrunner. No shortcuts—just all paths, end to end.

🛠️ PseudoCode

• Edge case: tree is empty? if (root == null) return empty list;
• Otherwise, begin DFS from root: dfs(node, path, resultList)
• At each non-null node:
  • Append your current node value to the path string.
  • If this is a leaf (left == null, right == null), slap the path onto the result list.
  • Otherwise, tack on “->” and keep passing the path down left and right branches.

  if (node.left == null && node.right == null) {
      result.add(path + node.val);
  } else {
      if (node.left != null) dfs(node.left, path + node.val + "->", result);
      if (node.right != null) dfs(node.right, path + node.val + "->", result);
  }

💻 The Code

// Binary tree node definition
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
 public class Solution {
    public List
<string> binaryTreePaths(TreeNode root) {
        List
<string> result = new ArrayList<>();
        if (root == null) return result;
        dfs(root, "", result);
        return result;
    }
    
    private void dfs(TreeNode node, String path, List
<string> result) {
        if (node.left == null && node.right == null) {
            result.add(path + node.val);
            return;
        }
        if (node.left != null) {
            dfs(node.left, path + node.val + "->", result);
        }
        if (node.right != null) {
            dfs(node.right, path + node.val + "->", result);
        }
    }
}
</string></string></string>

⚠️ Pitfalls, Traps & Runtime Smacks

• Only true leaves count. No shortcuts—node is a leaf only if both left and right are null. Don’t let imposters in your leaf club.
• Arrow-join mayhem: Avoid trailing arrows—no one wants to see “1->2->” at the end of a string.
• Empty trees are special: Return an empty list. Don’t manufacture fake paths out of existential despair.
• Stack nightmares: Java recursion isn’t infinite. Go iterative if you expect a tree taller than your patience (or 10k nodes).
• Time/space complexity: One visit per node, so O(n) time and output is proportional to number of leaves. No crazy hidden costs lurking.

🧠 Interviewer Brain-Tattoo

“Only a node with zero kids is leaf-enough to finish your path string. Don’t stop your walk through the tree just because you hit a one-parent wonder.”