Code Implementation

# 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: TreeNode) -> int:
        from collections import deque
        queue = deque([root])
        while queue:
            node = queue.popleft()
            # Add right first, then left, so leftmost node is last processed
            if node.right:
                queue.append(node.right)
            if node.left:
                queue.append(node.left)
        return node.val
      

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        std::queue<TreeNode*> q;
        q.push(root);
        TreeNode* node = nullptr;
        while (!q.empty()) {
            node = q.front();
            q.pop();
            // Right first, then left
            if (node->right) q.push(node->right);
            if (node->left) q.push(node->left);
        }
        return node->val;
    }
};
      

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode node = null;
        while (!queue.isEmpty()) {
            node = queue.poll();
            // Right first, then left
            if (node.right != null) queue.offer(node.right);
            if (node.left != null) queue.offer(node.left);
        }
        return node.val;
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var findBottomLeftValue = function(root) {
    let queue = [root];
    let node = null;
    while (queue.length) {
        node = queue.shift();
        // Right first, then left
        if (node.right) queue.push(node.right);
        if (node.left) queue.push(node.left);
    }
    return node.val;
};
      

Problem Description

You are given the root of a binary tree. Your task is to find the value of the leftmost node in the last (deepest) row of the tree. In other words, you need to return the value of the bottom-left node in the tree.

• There will always be at least one node in the tree.
• It is guaranteed that there is exactly one such leftmost value at the deepest level.
• The tree nodes are defined as TreeNode objects, each with val, left, and right properties.

Constraints: Only one valid solution exists for any given input. No node values are reused for this purpose.

Thought Process

To solve this problem, we need to identify the leftmost node at the deepest level of a binary tree. The brute-force idea is to traverse the entire tree, keep track of the depth, and record the first node we visit at each depth. At the end, the first node visited at the maximum depth is our answer.

However, there are multiple ways to traverse a tree: depth-first search (DFS) and breadth-first search (BFS). DFS can work, but requires careful tracking of depth and leftmost-ness. BFS, especially level-order traversal, naturally processes nodes level by level from left to right, making it easier to capture the leftmost node at each level.

An optimization is to process the tree level by level and, at each level, record the leftmost node. The last such node we record (at the deepest level) is the answer. Alternatively, we can process nodes in right-to-left order, so the last node processed is the bottom-left one.

Solution Approach

• Step 1: Use a queue to perform a breadth-first search (BFS) on the tree. This allows us to traverse the tree level by level.
• Step 2: Enqueue the root node as the starting point.
• Step 3: For each node dequeued, enqueue its children. To ensure that the leftmost node at the deepest level is processed last, add the right child first and then the left child. This way, the leftmost node at the deepest level will be the last node processed.
• Step 4: Continue this process until the queue is empty. The last node processed is the leftmost node at the deepest level.
• Step 5: Return the value of this node.

This approach is efficient because BFS ensures we cover all levels, and by enqueuing right before left, we guarantee the leftmost node at the bottom is processed last.

Example Walkthrough

Consider the following binary tree:

        2
       / \
      1   3
  

Step-by-step BFS (right-to-left):

1. Queue starts with [2]
2. Dequeue 2, enqueue 3 (right), then 1 (left). Queue is now [3, 1]
3. Dequeue 3, no children to enqueue. Queue is now [1]
4. Dequeue 1, no children to enqueue. Queue is now []
5. The last node processed is 1. So, the bottom-left value is 1.

This matches our expectation: the leftmost node at the last row is 1.

Time and Space Complexity

• Brute-force DFS: O(N) time (visit each node), O(H) space (recursion stack, where H is tree height).
• BFS Approach (Optimized): O(N) time (each node is visited once), O(W) space (queue can grow up to the width of the tree at the largest level).

Here, N is the total number of nodes, H is the height of the tree, and W is the maximum width of the tree.

Summary

The problem asks for the leftmost value in the last row of a binary tree. By leveraging a breadth-first search and processing children in right-to-left order, we can ensure the last node processed is the bottom-left node. This approach is efficient, elegant, and easy to implement, requiring only a standard queue and a single traversal of the tree.