# 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

| Item | Meaning |
|---|---|
| Input | The root of a binary tree |
| Output | An integer value |
| Goal | Return the leftmost value on the deepest level |
| Constraint | The tree has at least one node |

Function shape:

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

## Examples

Example 1:

```text
    2
   / \
  1   3
```

The last row is:

```text
1, 3
```

The leftmost value is:

```python
1
```

So the answer is:

```python
1
```

Example 2:

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

The last row is:

```text
7
```

So the answer is:

```python
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:

```text
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:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each node is visited once |
| Space | `O(w)` | The queue stores one level at a time |

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

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

## Implementation

```python
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:

```python
queue = deque([root])
```

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

Initialize the answer:

```python
answer = root.val
```

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

```python
answer = queue[0].val
```

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

Then process exactly one level:

```python
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:

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

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

After all levels are processed, return the final answer.

## Testing

```python
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:

| Test | Why |
|---|---|
| Balanced small tree | Checks a normal last row |
| Deeper mixed tree | Checks that deepest level wins |
| Single node | Minimum valid tree |
| Skewed left tree | Deepest node is on the left chain |
| Skewed right tree | Last row has one node, even on the right |