The O(n) Club: Find Bottom Left Tree Value — When Trees Won’t Hand You the Answer

The O(n) Club: Find Bottom Left Tree Value — When Trees Won’t Hand You the Answer

⚡ TL;DR

LeetCode 513: Want to find the leftmost value in the deepest row of a binary tree? Do a BFS (breadth-first search), keep saving that first node per level, and you win. Don’t queue up right kids before left—unless you like surprises.

// Java BFS snippet
Queue
<treenode> q = new LinkedList<>();
q.add(root);
int leftmost = root.val;
while (!q.isEmpty()) {
  int size = q.size();
  for (int i = 0; i < size; i++) {
    TreeNode node = q.poll();
    if (i == 0) leftmost = node.val;
    if (node.left != null) q.add(node.left);
    if (node.right != null) q.add(node.right);
  }
}
// leftmost is your answer
</treenode>

🧠 How Devs Usually Mess This Up

Plenty of ways to flop here—and no, none of them impress your interviewer:

• Enqueue right child before left: Congratulations, now you’re finding the rightmost bottom node. 10/10 for symmetry. 0/10 for reading comprehension.
• Returning the last node seen in BFS: That’s the rightmost again, unless your tree is just a stick.
• DFS: Update answer at every depth, regardless of direction—enjoy that semi-random result!

🔍 What’s Actually Going On

Picture your binary tree as a hotel: you want to deliver room service to the deepest, farthest-left room—because that guest is always hangry. There are two main ways you can pace the hallways:

• BFS: You cruise floor by floor, always peeking into the leftmost room first. The very first door you knock on at the last floor? That’s your target.
• DFS: You wander as deep as possible, always heading left before right. If you stumble into a new lowest floor, you write down the room’s number. Rinse, repeat, dodge stack overflows.

Just remember: interviews love remixing this one (“bottom right!”). If you rehearsed, you’re good. If not, enjoy the on-the-fly code acrobatics.

🛠️ PseudoCode

• Create a queue: Queue<TreeNode> q = new LinkedList<>();
• Add the root node.
• Loop while the queue’s not empty:
  • For every node on the current level:
  • If you’re at the first node in that round, update leftmost.
  • Add its left child to the queue first, then right child.
• The last leftmost you save is the winner.

// Java pseudocode flavor
Queue
<treenode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
  int levelSize = queue.size();
  for (int i = 0; i < levelSize; i++) {
    TreeNode node = queue.poll();
    if (i == 0) leftmost = node.val;
    if (node.left != null) queue.add(node.left);
    if (node.right != null) queue.add(node.right);
  }
}
</treenode>

• DFS? Track maxDepth. If you find a node at a deeper level, update your answer, then keep digging left before right.

💻 The Code

// BFS flavor — Java edition
public int findBottomLeftValue(TreeNode root) {
    Queue
<treenode> queue = new LinkedList<>();
    queue.add(root);
    int leftmost = root.val;
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            if (i == 0) leftmost = node.val;
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
    }
    return leftmost;
}
 // DFS flavor for recursion fans
int maxDepth = -1;
int leftmost;
public int findBottomLeftValue(TreeNode root) {
    dfs(root, 0);
    return leftmost;
}
private void dfs(TreeNode node, int depth) {
    if (node == null) return;
    if (depth > maxDepth) {
        maxDepth = depth;
        leftmost = node.val;
    }
    dfs(node.left, depth + 1);
    dfs(node.right, depth + 1);
}
</treenode>

⚠️ Pitfalls, Traps & Runtime Smacks

• Single root? No problem, your code’s ego survives unscathed.
• Super-skewed tree? BFS won’t flinch. DFS: stack overflow is just a breath away.
• Mixing up enqueue order? Results now brought to you by the chaos monkey.
• Complexity? O(n) time, O(n) space if you run into a broad last level. Just don’t tell your interviewer you could do “better.” You can’t.

🧠 Interviewer Brain-Tattoo

“Leftmost at the deepest level — unless you like your answers like your monitor’s stuck pixels: always a bit off.”