Find Bottom Left Tree Value
Find the leftmost value in the last (deepest) row of a binary tree.
- The number of nodes in the tree is in the range [1, 10⁴].
- -2³¹ <= Node.val <= 2³¹ - 1
Intuition
Find bottom left tree value returns the leftmost value on the deepest row of a binary tree. The name suggests walking left as far as possible, and that instinct is wrong in a way worth understanding.
A pure left-walk fails whenever the deepest level is only reachable by turning right somewhere higher up. Picture a root whose left child is a leaf, and whose right child has a left child of its own. The deepest row belongs to that right branch, so the answer sits below a right turn — a left-walk never reaches it:
- The question is about depth first and leftness second, so depth must be resolved before position.
BFS handles that naturally, because it processes the tree level by level. Track the first node of each level, and when the queue empties, the last one recorded is on the deepest row and is its leftmost node.
A neater version drops the first-node bookkeeping entirely: enqueue the right child before the left. Then the final node dequeued overall is the leftmost of the deepest level, and a single variable overwritten on every dequeue holds the answer when the loop ends.
The DFS alternative works too — track depth and record a node only when it reaches a strictly greater depth than any seen so far. Traversing left first means the first node at each new depth is its leftmost. The strictness matters: using >= would let a later, more rightward node at the same depth overwrite the correct answer.
Level-order traversal recording the first node of each level. The last such value written belongs to the deepest level, so no depth tracking is needed — the loop's natural termination identifies the bottom row.
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for O(n) time and O(w) space.
Reject the pure left-walk
Following left children fails when the deepest row lies under a right turn higher up. Depth must be settled before leftness, and this counterexample is the point of the problem.
Traverse level by level
BFS processes nodes in increasing depth order, so the last level it reaches is the deepest. That ordering is what lets the answer be identified without knowing the tree's height in advance.
Record the first node of each level
Snapshot the queue size before each round and keep the first node dequeued. When the queue empties, the last recorded candidate is the leftmost node of the deepest level.
Or enqueue right before left
Pushing the right child first makes the final node dequeued overall the leftmost of the deepest row. A single variable overwritten each iteration then holds the answer, with no level bookkeeping at all.
Use strict depth comparison in the DFS version
Traverse left first, recording a node only when its depth is strictly greater than any seen. Using >= lets a more rightward node at the same depth overwrite the correct answer.
Cost of the traversal
Every node is visited once, giving O(n) time. BFS uses O(w) space for the queue, where w is the widest level; DFS uses O(h) for the recursion stack.
Solution & live demo
Common pitfalls
Not capturing the level size before popping
while queue:
node = queue.popleft()
...size = len(queue) for i in range(size):
The queue grows while the level is processed, so its length changes mid-loop. Snapshotting the size first is what keeps levels separated and makes i == 0 mean "leftmost of this level".
Enqueuing the right child first
if node.right: queue.append(node.right) if node.left: queue.append(node.left)
if node.left: queue.append(node.left) if node.right: queue.append(node.right)
The i == 0 test relies on left-to-right ordering within each level. Reversing the insertion makes it record the bottom-right value instead.
Returning the first node of the last level found by DFS depth
if depth > maxDepth: maxDepth = depth; ans = node.val
if i == 0: leftmost = node.val
DFS works but only if it descends left-first and uses strict > so later same-depth nodes don't overwrite. BFS makes the leftmost-of-deepest property structural rather than something to get right.
Edge cases
Root is both the first and last level's leftmost value.
BFS still records it correctly as that level's first-popped node -- a left-walk DFS would miss it.
Leftmost of the last level is simply the tree's normal bottom-left leaf.
Every level has exactly one node, so each level's candidate is trivially correct.