Find Bottom Left Tree Value - Solution & Explanation

Problem Overview: Given the root of a binary tree, return the value of the leftmost node in the last row of the tree. The challenge is identifying the first node that appears at the deepest level while traversing the tree efficiently.

This problem is a classic traversal task on a tree. Since the target node depends on depth and position, both level-order and depth-first traversal strategies work well. The goal is to track which node appears first at the deepest level.

Approach 1: Breadth-First Search (BFS) Level Order Traversal (O(n) time, O(w) space)

Breadth-first traversal processes the tree level by level using a queue. The key idea is that the first node you encounter at each level is the leftmost node. While performing level-order traversal, record the first element of every level and keep updating it as you move deeper. When the traversal finishes, the stored value from the last processed level is the answer.

Implementation uses a queue where each iteration processes all nodes currently in the queue (one level). The first node in that iteration represents the leftmost node for that depth. BFS is intuitive for problems involving level-based properties because it naturally groups nodes by depth. Time complexity is O(n) since every node is visited once, and space complexity is O(w), where w is the maximum width of the tree due to the queue.

This approach relies on Breadth-First Search and is usually the most straightforward way to reason about level-specific values.

Approach 2: Depth-First Search (DFS) with Depth Tracking (O(n) time, O(h) space)

Depth-first traversal explores the tree recursively while tracking the current depth. The trick is to traverse the left subtree before the right subtree and update the answer whenever you encounter a node at a depth greater than any previously visited depth. Because the recursion visits left children first, the first node encountered at a new depth will always be the leftmost node.

You maintain two variables: maxDepth and bottomLeftValue. When the recursion reaches a node deeper than maxDepth, update both variables. Continue exploring the tree until all nodes are processed. This ensures the first node discovered at the deepest level is stored.

This strategy uses Depth-First Search recursion. Time complexity remains O(n) because each node is visited once. Space complexity is O(h), where h is the height of the tree due to the recursion stack. For balanced trees this is O(log n), but in worst-case skewed trees it becomes O(n).

Recommended for interviews: BFS is often the quickest solution to explain because the problem explicitly refers to the "last row" of the tree, which maps directly to level-order traversal. DFS shows deeper understanding of recursion and depth tracking. Strong candidates usually mention both approaches and implement the one they are most comfortable with.