LeetCode 513: Find Bottom Left Tree Value

Problem Restatement

We are given the root of a binary tree.

We need to return the leftmost value in the last row of the tree.

The last row means the deepest level of the tree. The leftmost value means the first node on that deepest level when reading from left to right.

The official problem asks us to return the leftmost value in the last row of a binary tree.

Input and Output

Function shape:

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        ...

Examples

Example 1:

    2
   / \
  1   3

The last row is:

1, 3

The leftmost value is:

1

So the answer is:

1

Example 2:

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

The last row is:

7

So the answer is:

7

This matches the common example for the problem, where root = [1,2,3,4,null,5,6,null,null,7] returns 7.

First Thought: Traverse the Tree by Levels

Because the problem asks about the last row, level-order traversal is a natural fit.

Level-order traversal visits the tree row by row:

top level
then next level
then next level
...

If we process one level at a time, then the first node of each level is its leftmost node.

So we can keep updating the answer to the first node of the current level. After the traversal ends, the answer will be the leftmost value of the deepest level.

Key Insight

Use BFS with a queue.

At the beginning of each level, the queue contains exactly the nodes of that level, from left to right.

Therefore:

queue[0].val

is the leftmost value of the current level.

If we update answer to this value before processing each level, the final value of answer will come from the last level.

Algorithm

Create a queue initialized with the root.

While the queue is not empty:

1. Save the first node value in the queue as answer.
2. Process all nodes currently in the queue.
3. Add each node’s left child, then right child, to the queue.

When the loop finishes, return answer.

Correctness

BFS processes the tree level by level.

At the start of each loop iteration, the queue contains all nodes on the current level in left-to-right order.

So the first node in the queue is exactly the leftmost node of that level.

The algorithm stores that value in answer.

Since the loop continues until all levels are processed, the final update to answer happens at the deepest level of the tree.

Therefore, when the algorithm returns answer, it returns the leftmost value in the last row.

Complexity

Here, n is the number of nodes and w is the maximum width of the tree.

In the worst case, w = O(n).

Implementation

from typing import Optional
from collections import deque

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        queue = deque([root])
        answer = root.val

        while queue:
            answer = queue[0].val

            for _ in range(len(queue)):
                node = queue.popleft()

                if node.left:
                    queue.append(node.left)

                if node.right:
                    queue.append(node.right)

        return answer

Code Explanation

Initialize the queue with the root:

queue = deque([root])

The problem guarantees that the tree has at least one node, so root is valid.

Initialize the answer:

answer = root.val

At the start of each level, update answer to the first node in the queue:

answer = queue[0].val

This works because the queue is ordered from left to right.

Then process exactly one level:

for _ in range(len(queue)):

The call to len(queue) is evaluated before the loop begins, so newly added child nodes belong to the next level.

For each node, add its children from left to right:

if node.left:
    queue.append(node.left)

if node.right:
    queue.append(node.right)

After all levels are processed, return the final answer.

Testing

def test_find_bottom_left_value():
    s = Solution()

    # Tree:
    #     2
    #    / \
    #   1   3
    root = TreeNode(2)
    root.left = TreeNode(1)
    root.right = TreeNode(3)
    assert s.findBottomLeftValue(root) == 1

    # Tree:
    #         1
    #        / \
    #       2   3
    #      /   / \
    #     4   5   6
    #        /
    #       7
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.right.left = TreeNode(5)
    root.right.right = TreeNode(6)
    root.right.left.left = TreeNode(7)
    assert s.findBottomLeftValue(root) == 7

    # Single node
    root = TreeNode(10)
    assert s.findBottomLeftValue(root) == 10

    # Skewed left
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.left.left = TreeNode(3)
    assert s.findBottomLeftValue(root) == 3

    # Skewed right
    root = TreeNode(1)
    root.right = TreeNode(2)
    root.right.right = TreeNode(3)
    assert s.findBottomLeftValue(root) == 3

    print("all tests passed")

Test meaning: