LeetCode #513 Medium

Find Bottom Left Tree Value

Find the leftmost value in the last (deepest) row of a binary tree.

treebfs

02

Intuition

💡

Walking left as far as possible sounds like it should find the bottom-left value, but it can land on the wrong node entirely: the deepest level might only be reachable by turning RIGHT somewhere higher up, and a pure left-walk never gets there. The fix is to level-order the whole tree and, on each level, remember only the FIRST node popped -- since BFS processes a level strictly left to right, that first node is that level's leftmost value. The last level recorded, once the queue empties, holds the answer; equivalently you could BFS right-to-left and just keep the final node touched.

03

Approach

1

BFS level by level

Process the queue one full level at a time, tracking the size of the current level before draining it.

2

Keep the first node of each level

The node popped at index 0 within a level's batch is, by BFS's left-to-right processing order, that level's leftmost node -- remember its value as the current candidate.

3

The last candidate wins

After the queue empties, whichever candidate was recorded on the final (deepest) level is the answer -- no explicit depth tracking of 'is this the deepest' is needed, since each level simply overwrites the last.

04

Solution & live demo

python

▶1from collections import deque
▶2 
▶3class Solution:
▶4    def findBottomLeftValue(self, root):
▶5        queue = deque([root])
▶6        leftmost = root.val
▶7        while queue:
▶8            size = len(queue)
▶9            for i in range(size):
▶10                node = queue.popleft()
▶11                if i == 0:
▶12                    leftmost = node.val
▶13                if node.left:
▶14                    queue.append(node.left)
▶15                if node.right:
▶16                    queue.append(node.right)
▶17        return leftmost

05

Edge cases

Single node

Root is both the first and last level's leftmost value.

Deepest node reached only via a right turn

BFS still records it correctly as that level's first-popped node -- a left-walk DFS would miss it.

Complete tree

Leftmost of the last level is simply the tree's normal bottom-left leaf.

All nodes on one side (skewed)

Every level has exactly one node, so each level's candidate is trivially correct.

06

Complexity

Time

O(n)

Space

O(w)

w is the maximum width of the tree, bounding the queue size.