algoadvance

You are given the root of a binary tree. Find the value of the leftmost node in the last row of the tree.

Return the leftmost value in the last row of the tree.

Example:

Input: root = [2,1,3]
Output: 1

Constraints:

• The number of nodes in the tree is in the range [1, 10^4].
• -2^31 <= Node.val <= 2^31 - 1

Clarifying Questions

1. What defines the last row in a binary tree?
   • The last row refers to the deepest level of the tree. If there are multiple nodes at this level, we need the leftmost one.
2. Can the tree have only one node?
   • Yes, in which case the value of that node is the answer.

Strategy

We will use a Breadth-First Search (BFS) approach to solve this problem. BFS is well-suited for this task because it explores nodes level by level from left to right. This way, when we reach the last level of the tree, we can simply record the first node’s value encountered at that level.

1. Initialize a queue: Start by adding the root node to the queue.
2. Iterate through the queue:
   • For each node, check if it has left and right children and add them to the queue.
   • Keep track of the value of the first node encountered in the current level.
3. Continue until the queue is empty: The last recorded value from the last level would be the desired result.

Code

Here’s the code to achieve the above strategy:

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

def findBottomLeftValue(root: TreeNode) -> int:
    if not root:
        return -1  # Edge case handling

    queue = deque([root])
    # To store the leftmost value of the last row
    leftmost_value = root.val
    
    while queue:
        # Number of nodes at the current level
        num_nodes_at_level = len(queue)
        for i in range(num_nodes_at_level):
            node = queue.popleft()
            # For the first node in this level, set the leftmost_value
            if i == 0:
                leftmost_value = node.val
            # Add child nodes of the current node into the queue
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
                
    return leftmost_value

Time Complexity

• Time Complexity: (O(N))
  • Each node is processed exactly once, where (N) is the number of nodes in the tree.
• Space Complexity: (O(W))
  • The maximum width of the binary tree is the limiting factor for the queue size, where (W) is the maximum number of nodes at any level in the tree. In the worst case, (W = \frac{N}{2}) for a perfect binary tree. Hence, the space complexity is (O(N)) in the worst case.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?