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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Bottom Left Tree Value

Number: 513

Difficulty: Medium

Paid? No

Companies: josh technology, Bloomberg, Adobe, Microsoft

Problem Description

We are given the root of a binary tree. The task is to find and return the leftmost value in the last row (i.e., the bottom level) of the tree.

Key Insights

  • Use level order traversal (BFS) to systematically process the tree level by level.
  • The first element of each level is the leftmost node for that level.
  • By updating the leftmost value at each level and finishing the traversal, the last updated value corresponds to the leftmost node in the bottom-most level.
  • An alternative approach using DFS can also be used by tracking depth and updating the result when reaching a new maximum depth.

Space and Time Complexity

Time Complexity: O(n) – Every node in the tree is visited exactly once. Space Complexity: O(m) – Where m is the maximum number of nodes at any level (in the worst-case scenario, this can be O(n)).

Solution

We can solve this problem using the Breadth-First Search (BFS) algorithm by leveraging a queue data structure. For each level, we record the value of the first node, which is the leftmost node for that level. When the BFS completes, the recorded value from the last level is our answer. This approach efficiently processes the tree in level order, ensuring that all nodes are visited and the correct value is returned.

Code Solutions

# Python implementation for finding the bottom left tree value

from collections import deque

def findBottomLeftValue(root):
    # Initialize a queue for level order traversal (BFS)
    queue = deque([root])
    leftmost_value = root.val

    # Process nodes level by level
    while queue:
        level_size = len(queue)
        # The first node in the level is the leftmost node
        leftmost_value = queue[0].val
        for _ in range(level_size):
            node = queue.popleft()
            # Enqueue left child first to maintain left-to-right order
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return leftmost_value
← Back to All Questions