513. Find Bottom Left Tree Value

Medium LeetCode

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

Example 1

Input: root = [2,1,3]

Output: 1

Example 2

Input: root = [1,2,3,4,null,5,6,null,null,7]

Output: 7

Constraints

• The number of nodes in the tree is in the range [1, 104]
• -231 <= Node.val <= 231 - 1

How to solve the problem

Code

• BFS

# 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: Optional[TreeNode]) -> int:
        # Initialize a queue with the root node
        # We will use BFS (breadth-first search), but process right child first!
        q = deque([root])

        # Perform BFS traversal
        while q:
            # Pop the current node from the front of the queue
            node = q.popleft()

            # IMPORTANT: Add right child first
            # This ensures that the last node we visit will be the bottom-left node
            if node.right: 
                q.append(node.right)

            # Add left child
            if node.left: 
                q.append(node.left)

        # After the loop, 'node' will point to the last node visited,
        # which is the bottom-left value of the tree
        return node.val

Complexity

• Time complexity: O(n), n == number of nodes
• Space complexity: O(n)