Find Bottom Left Tree Value

Find Bottom Left Tree Value

What is this problem about?

The Find Bottom Left Tree Value interview question asks you to find the value of the leftmost node in the very last row of a binary tree. The "last row" is the row with the maximum depth. Even if there are nodes on the left in higher rows, you are specifically looking for the one at the deepest level.

Why is this asked in interviews?

Microsoft and Amazon frequently use this problem to evaluate a candidate's mastery of tree traversal techniques. It tests whether you can distinguish between different levels of a tree. It evaluation your proficiency with both the Breadth-First Search interview pattern and the Depth-First Search interview pattern. While both work, the BFS approach is often considered more intuitive for "row-by-row" properties.

Algorithmic pattern used

There are two main approaches:

1. BFS (Level Order Traversal): Traverse the tree level by level. At each level, the first node you visit is the leftmost. Update a result variable at the start of every new level.
   • Optimization: Perform BFS from right to left (process right child before left). The very last node you visit in the entire BFS will be the bottom-left one.
2. DFS: Perform a traversal while keeping track of the current depth and the maximum depth seen so far. When you reach a node at a depth greater than the maxDepth, update the maxDepth and the resultValue.

Example explanation

Consider this tree:

    1
   / 
  2   3
 /   / 
4   5   6
     
      7

1. Level 0: [1].
2. Level 1: [2, 3].
3. Level 2: [4, 5, 6]. Leftmost is 4.
4. Level 3: [7]. Leftmost is 7. Final bottom-left value is 7.

Common mistakes candidates make

• Returning the leftmost leaf: Thinking any leaf node on the far left is the answer, even if it's not in the deepest row.
• Forgetting depth tracking: In DFS, failing to update the result only when a strictly greater depth is reached.
• Queue order: In the right-to-left BFS trick, accidentally processing left before right, which would give the bottom-right value.

Interview preparation tip

The "Right-to-Left BFS" is a clever trick that makes the code for this problem extremely short. Instead of tracking levels, just push the right child then the left child to the queue. The last node popped is always the bottom-left.