The O(n) Club: Binary Tree Preorder Traversal—How Not to Trip Over Your Roots

The O(n) Club: Binary Tree Preorder Traversal—How Not to Trip Over Your Roots

⚡ TL;DR

Preorder traversal means hitting every node in a binary tree by first visiting the root, then the left child, then the right. Fastest way to look busy in an interview. Here’s the, ahem, “hello world” of tree traversals in Java:

// Recursion: the Java developer's comfort food
void preorder(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val + " ");
    preorder(root.left);
    preorder(root.right);
}

🧠 How Devs Usually Mess This Up

Raise your hand if you’ve ever confidently explained preorder as left-root-right (wrong). Most beginners trip up on traversal orders or—if feeling fancy—reverse the push order in iterative implementations (pro tip: it’s right then left, or chaos reigns). And for those daring enough to try Morris traversal, nothing like accidentally turning your tree into an unsolvable escape room for the next engineer.

🔍 What’s Actually Going On

Think of preorder like a tour through a mansion where, before you do anything, you announce yourself in every room you enter (the root), then inspect the left wing, THEN the right. Recursion? That’s just a butler with a photographic memory. Iteration? To-do list with priority stacking. Morris traversal? Rearranging the secret passageways for dramatic effect—but don’t forget to put everything back or housekeeping (your tech lead) will throw things.

🛠️ PseudoCode

• Recursive (a.k.a. “Yeah, sure, I trust the call stack”):

  void preorder(node):
      if node == null: return
      visit(node)
      preorder(node.left)
      preorder(node.right)
      // Done, Java cleans up your mess
  

• Iterative (Stack, because you want control):

  stack.push(root)
  while stack not empty:
      node = stack.pop()
      visit(node)
      if node.right != null: stack.push(node.right)
      if node.left != null: stack.push(node.left)
  

  Push right, then left, because a stack is Last-In-First-Out and the left child must be handled first.
• Morris Traversal (Space? Never heard of her):

  curr = root
  while curr != null:
      if curr.left == null:
          visit(curr)
          curr = curr.right
      else:
          pred = curr.left
          while pred.right != null and pred.right != curr:
              pred = pred.right
          if pred.right == null:
              visit(curr)
              pred.right = curr
              curr = curr.left
          else:
              pred.right = null
              curr = curr.right
  

  You temporarily hijack right pointers, then put them back—don’t lose anyone’s keys!

💻 The Code

// Make your interviewer happy with all the flavors:
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}
 // 1. Recursion
void preorderRecursive(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val + " ");
    preorderRecursive(root.left);
    preorderRecursive(root.right);
}
 // 2. Iterative (Java Stack)
void preorderIterative(TreeNode root) {
    if (root == null) return;
    Stack
<treenode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        System.out.print(node.val + " ");
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
}
 // 3. Morris Traversal (O(1) Space — Hacker Bonus)
void preorderMorris(TreeNode root) {
    TreeNode curr = root;
    while (curr != null) {
        if (curr.left == null) {
            System.out.print(curr.val + " ");
            curr = curr.right;
        } else {
            TreeNode pred = curr.left;
            while (pred.right != null && pred.right != curr) pred = pred.right;
            if (pred.right == null) {
                System.out.print(curr.val + " ");
                pred.right = curr;
                curr = curr.left;
            } else {
                pred.right = null;
                curr = curr.right;
            }
        }
    }
}
</treenode>

⚠️ Pitfalls, Traps & Runtime Smacks

• Null roots: Don’t dereference your way into an NPE support ticket.
• Reversed stack order? Have fun traversing the right side before the left (makes for wild interview stories).
• Morris traversal: Forget to repair those right pointers and your next method will see a horror show instead of a tree.
• Recursion: JVM stacks are not bottomless. Tall, skinny trees = StackOverflowError, and not the “good” kind.
• O(n) time for everyone; O(h) space for recursion/iteration (h = tree height), O(1) for Morris traversal—that is, if you don’t set your tree on fire.

🧠 Interviewer Brain-Tattoo

“When in doubt: go root, then left, then right—like every polite developer tour should.”