We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Bottom Left Tree Value

Difficulty: Medium

Problem Description

Given the root of a binary tree, return the leftmost value in the last row of the tree.

Key Insights

  • The last row of a binary tree contains all the leaf nodes.
  • To find the leftmost value in the last row, we can utilize a level order traversal (BFS) to explore all nodes level by level.
  • By iterating through each level, we can keep track of the first node we encounter at the last level.

Space and Time Complexity

Time Complexity: O(N) - where N is the number of nodes in the tree, as we need to visit each node once. Space Complexity: O(W) - where W is the maximum width of the tree, which is the maximum number of nodes at any level.

Solution

We can use a breadth-first search (BFS) approach with a queue to explore each level of the tree. As we traverse each level, we keep track of the leftmost value seen at the last level. The queue will help us process nodes level by level, and we will update our leftmost value each time we reach a new level.

Code Solutions

from collections import deque

def findBottomLeftValue(root):
    if not root:
        return None
    
    queue = deque([root])
    leftmost_value = None
    
    while queue:
        leftmost_value = queue[0].val  # The first element in the queue is the leftmost for this level
        level_size = len(queue)
        
        for _ in range(level_size):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    return leftmost_value
← Back to All Questions