The O(n) Club: Binary Tree Level Order Traversal II – Boss Mode Unlocked

The O(n) Club: Binary Tree Level Order Traversal II – Boss Mode Unlocked

⚡ TL;DR

Need to traverse a tree from leaf to root, level by level? Use BFS, gather each level’s nodes, then reverse your list at the end. No need for recursive trapeze acts—just use that queue like a civilized dev. Quick Java taste:

// Binary Tree Level Order Traversal II
public List<list>> levelOrderBottom(TreeNode root) {
    List<list>> res = new ArrayList<>();
    if (root == null) return res;
    Queue
<treenode> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
        int sz = q.size();
        List
<integer> lvl = new ArrayList<>();
        for (int i = 0; i < sz; i++) {
            TreeNode n = q.poll();
            lvl.add(n.val);
            if (n.left != null) q.add(n.left);
            if (n.right != null) q.add(n.right);
        }
        res.add(lvl);
    }
    Collections.reverse(res);
    return res;
}</integer></treenode></list></list>

🧠 How Devs Usually Mess This Up

Let’s start with the DFS crowd: if you think every tree needs recursion, this’ll recalibrate your chakras. Level order means BFS—queues, not stack nightmares. Oh, and don’t flip the order inside each level—just reverse the whole list of levels after BFS. Building it backwards as you go? That’s how you get a forehead-sized bug list.

🔍 What’s Actually Going On

Imagine you’re writing an office memo: you normally start from the CEO (root), but this week the interns want a voice. So, you gather everyone’s opinion by floor—from the lobby up—then, just before publishing, you flip the order so the most junior voices come first. Traverse top-down, but report bottom-up. Simple.

🛠️ PseudoCode

• Initialize: Use a queue for nodes, a results list for levels.
  

  Queue<treenode> queue = new LinkedList<>();
  List<List<Integer>> res = new ArrayList<>();</treenode>

• BFS by level: For each queue round, collect all node values (one level), enqueue their kids.
  

  while (!queue.isEmpty()) {
      int sz = queue.size();
      List<Integer> lvl = new ArrayList<>();
      for (int i = 0; i < sz; i++) {
          TreeNode n = queue.poll();
          lvl.add(n.val);
          if (n.left != null) queue.add(n.left);
          if (n.right != null) queue.add(n.right);
      }
      res.add(lvl);
  }

• Reverse: After all levels collected, flip the result.
  

  Collections.reverse(res);

💻 The Code

// The Actual Java
public List<list>> levelOrderBottom(TreeNode root) {
    List<list>> res = new ArrayList<>();
    if (root == null) return res;
    Queue
<treenode> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
        int sz = q.size();
        List
<integer> lvl = new ArrayList<>();
        for (int i = 0; i < sz; i++) {
            TreeNode n = q.poll();
            lvl.add(n.val);
            if (n.left != null) q.add(n.left);
            if (n.right != null) q.add(n.right);
        }
        res.add(lvl);
    }
    Collections.reverse(res);
    return res;
}
// Definition for a binary tree node:
public class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}</integer></treenode></list></list>

⚠️ Pitfalls, Traps & Runtime Smacks

• No point reversing inside levels—it’s just busywork for your CPU.
• DFS for level order? Not today, recursion-overlords.
• Null root? Return empty list. Boom, done.
• Time and space: Each node is visited, so O(N) for everything. Java’s queue and array handling make this painless.

🧠 Interviewer Brain-Tattoo

“If you ever feel lost in tree traversals, just remember: queues get you level order, and a last-minute reverse keeps HR happy.”