Find Bottom Left Tree Value

This problem requires us to find the leftmost value in the last row of a binary tree.

We can solve this problem using a level-order traversal (also known as breadth-first search). This method involves traversing the tree level by level, starting from the root. We use a queue to keep track of nodes to visit. For each node, we first insert its left child into the queue, then its right child. This ensures that we visit the leftmost node of each level first.

Here is the Python code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

from collections import deque

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        queue = deque([root])
        while queue:
            node = queue.popleft()
            if node.right:
                queue.append(node.right)
            if node.left:
                queue.append(node.left)
        return node.val

In this code, queue is a double-ended queue that starts with the root of the tree. We then enter a loop that continues until the queue is empty. In each iteration of the loop, we remove the next node from the front of the queue, then add its right child and its left child to the back of the queue. Since we add the right child first, we ensure that the left child will be visited first in the next level. When the queue is empty, node is the leftmost node of the last level, so we return its value.

This solution has a time complexity of O(n), where n is the number of nodes in the tree, because we visit each node once. Its space complexity is O(m), where m is the maximum width of the tree, because in the worst case, all nodes of a level could be in the queue simultaneously. This is an efficient solution given the constraints (the number of nodes in the tree is in the range [1, 10^4]).