Problem Description

You are given the root of a binary tree. Your task is to find the value of the leftmost node in the bottom-most (last) row of the tree.

The problem asks you to:

1. Identify the last row of the binary tree (the deepest level)
2. Find the leftmost node in that row
3. Return the value of that node

For example, if you have a binary tree like:

      1
     / \
    2   3
   /   / \
  4   5   6

The last row contains nodes 4, 5, and 6. The leftmost value in this row is 4, so you would return 4.

The solution uses a level-order traversal (BFS) approach with a queue. It processes the tree level by level, and for each level, it captures the first node's value (which is the leftmost node of that level). By the time the traversal completes, ans will hold the leftmost value of the last row encountered.

The key insight is that when using BFS with a queue, the first element in the queue at the start of processing each level is always the leftmost node of that level. The algorithm keeps updating ans with this leftmost value for each level, so when it finishes, ans contains the leftmost value of the deepest level.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph where each node has at most two children and there are no cycles.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure.

DFS

• Yes: We arrive at DFS as the recommended approach for tree problems.

Conclusion: The flowchart suggests using DFS (Depth-First Search) for this tree problem.

While the provided solution uses BFS (level-order traversal with a queue), DFS is equally valid and follows the flowchart's recommendation. With DFS, we can traverse the tree while tracking the depth of each node. We maintain variables for the maximum depth seen so far and the leftmost value at that depth. When we encounter a node at a deeper level than previously seen, or when we encounter the first node at the current maximum depth (which would be the leftmost due to the traversal order), we update our answer.

The DFS approach would involve:

1. Traversing the tree recursively
2. Tracking the current depth during traversal
3. Updating the leftmost value whenever we reach a new maximum depth
4. Prioritizing left subtree traversal before right to ensure we capture the leftmost node first at each level

Both DFS and BFS are valid approaches for this problem, with the flowchart naturally leading us to consider DFS for tree-based problems.

Intuition

The key insight is that we need to find the leftmost value in the deepest level of the tree. This naturally suggests we need to explore the tree level by level to identify which level is the deepest, and within that level, which node appears first from the left.

When we think about traversing a tree level by level, BFS (Breadth-First Search) immediately comes to mind because it processes all nodes at depth d before moving to nodes at depth d+1. This gives us a natural way to identify the last level - it's simply the final set of nodes we process.

For each level during BFS traversal, the nodes are processed from left to right because:

1. We add the left child before the right child to the queue
2. The queue maintains this left-to-right ordering naturally

The clever part of the solution is recognizing that at the start of processing each level, q[0] (the first element in the queue) is always the leftmost node of that level. Instead of storing all nodes of each level or tracking which level is the last, we simply update our answer with q[0].val at the beginning of each level's processing.

By continuously updating ans with the leftmost value of each level as we traverse, we guarantee that when the traversal completes, ans holds the leftmost value of the deepest level we encountered. This is elegant because:

• We don't need to explicitly track the depth
• We don't need to store all values of the last level
• We get the answer in a single pass through the tree

The solution essentially transforms the problem from "find the leftmost value in the last row" to "keep track of the leftmost value of the current level, and the final value will be from the last row."

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Solution Approach

The solution implements a level-order traversal using BFS with a queue data structure. Here's how the implementation works:

1. Initialize the Queue: Start with a deque containing just the root node: q = deque([root]). We use a deque for efficient pop operations from the left.

2. Initialize the Answer: Set ans = 0 to store the leftmost value of the current level being processed.

3. Process Each Level: The outer while q: loop continues as long as there are nodes to process. Each iteration of this loop represents processing one complete level of the tree.

4. Capture Leftmost Value: At the start of processing each level, immediately capture the value of the leftmost node: ans = q[0].val. This is the key step - q[0] is always the leftmost node of the current level.

5. Process All Nodes in Current Level: The inner for _ in range(len(q)): loop ensures we process exactly the nodes that belong to the current level. The len(q) at the start of the level tells us how many nodes are in this level.

6. Add Children for Next Level: For each node in the current level:

   • Pop the node from the left: node = q.popleft()
   • Add its children to the queue (left child first, then right child):

     if node.left:
         q.append(node.left)
     if node.right:
         q.append(node.right)

   • The order matters here - adding left before right ensures the next level maintains left-to-right ordering.

7. Return the Final Answer: After all levels are processed, ans contains the leftmost value from the last level encountered, which is exactly what we need to return.

The algorithm's time complexity is O(n) where n is the number of nodes, as we visit each node exactly once. The space complexity is O(w) where w is the maximum width of the tree, which represents the maximum number of nodes at any level stored in the queue at once.

Example Walkthrough

Let's walk through the solution with a small binary tree example:

      2
     / \
    1   3
   /   
  4   
 / \
5   6

We want to find the leftmost value in the bottom row. The bottom row here is [5, 6], so our answer should be 5.

Initial State:

• Queue: [2] (contains root)
• ans: 0

Level 1 (root level):

• Before processing: q = [2]
• Update ans: ans = q[0].val = 2 (leftmost of this level)
• Process node 2:
  • Pop 2 from queue
  • Add children: left child 1, right child 3
• After level: q = [1, 3]

Level 2:

• Before processing: q = [1, 3]
• Update ans: ans = q[0].val = 1 (leftmost of this level)
• Process 2 nodes (original queue length):
  • Process node 1:
    • Pop 1 from queue
    • Add child: left child 4
  • Process node 3:
    • Pop 3 from queue
    • No children to add
• After level: q = [4]

Level 3:

• Before processing: q = [4]
• Update ans: ans = q[0].val = 4 (leftmost of this level)
• Process 1 node:
  • Process node 4:
    • Pop 4 from queue
    • Add children: left child 5, right child 6
• After level: q = [5, 6]

Level 4 (last level):

• Before processing: q = [5, 6]
• Update ans: ans = q[0].val = 5 (leftmost of this level)
• Process 2 nodes:
  • Process node 5:
    • Pop 5 from queue
    • No children to add
  • Process node 6:
    • Pop 6 from queue
    • No children to add
• After level: q = [] (empty)

Result: The queue is empty, so we exit the loop. The variable ans = 5, which is indeed the leftmost value in the bottom row of the tree.

The key insight demonstrated here is that at the start of processing each level, q[0] always gives us the leftmost node of that level. By continuously updating ans with this value, we ensure that after processing all levels, ans contains the leftmost value from the deepest level.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the total number of nodes in the binary tree. The algorithm performs a level-order traversal (BFS) visiting each node exactly once. Each node is enqueued and dequeued once, and both operations take O(1) time. Therefore, the overall time complexity is O(n).

Space Complexity: O(w) where w is the maximum width of the binary tree (the maximum number of nodes at any level). In the worst case, this occurs at the last level of a complete binary tree, where the width can be up to n/2 nodes, making the space complexity O(n) in the worst case. In the best case (a skewed tree), the space complexity would be O(1) as there would be at most one node at each level.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Preserving Level Boundaries

A common mistake is trying to find the leftmost value without properly tracking level boundaries. Some might attempt to simply traverse the tree and keep track of the "deepest leftmost" node without using proper level-order traversal:

Incorrect Approach:

def findBottomLeftValue(self, root):
    queue = deque([root])
    leftmost = root.val
  
    while queue:
        node = queue.popleft()
        # This doesn't guarantee we're getting the leftmost of the bottom row
        if node.left:
            queue.append(node.left)
            leftmost = node.left.val
        if node.right:
            queue.append(node.right)
            if not node.left:  # Wrong logic
                leftmost = node.right.val
  
    return leftmost

Why it fails: This approach doesn't properly identify which nodes belong to the last level, and the logic for determining "leftmost" is flawed.

2. Incorrect Order of Child Addition

Adding children in the wrong order (right before left) will break the left-to-right ordering in the queue:

Incorrect Code:

# Wrong order - adds right child before left child
if current_node.right:
    queue.append(current_node.right)
if current_node.left:
    queue.append(current_node.left)

Solution: Always add the left child first, then the right child to maintain proper left-to-right ordering in each level.

3. Capturing Leftmost Value at Wrong Time

Some might try to capture the leftmost value after processing nodes or at the wrong point in the iteration:

Incorrect Timing:

while queue:
    level_size = len(queue)
    for i in range(level_size):
        current_node = queue.popleft()
        if i == 0:  # Capturing after popleft - node is already removed!
            leftmost_value = current_node.val
        # ... rest of code

Solution: Capture queue[0].val before starting to process (popleft) any nodes in the current level. This ensures you're getting the actual leftmost node that's still in the queue.

4. Using Wrong Queue Operations

Using a regular list with pop(0) instead of deque with popleft():

Inefficient Code:

queue = [root]  # Regular list
while queue:
    node = queue.pop(0)  # O(n) operation!

Solution: Use collections.deque with popleft() for O(1) removal from the front of the queue, making the overall algorithm more efficient.

5. Forgetting Edge Cases

Not handling the guaranteed constraint that root is not None. While the problem guarantees a non-null root, defensive programming might lead to unnecessary checks:

Overly Defensive:

def findBottomLeftValue(self, root):
    if not root:  # Unnecessary given problem constraints
        return 0  # or raise exception
    # ... rest of code

Solution: Trust the problem constraints. The problem states the tree has at least one node, so the root will never be None. Focus on the core algorithm instead of adding unnecessary edge case handling.