#513

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Find Bottom Left Tree Value

Find the leftmost value in the last row of a binary tree using efficient traversal strategies.

tree depth first search breadth first search binary tree

Problem Statement

Given the root of a binary tree, the task is to return the leftmost value in the last row of the tree. The bottom-left tree value is the leftmost node that is the deepest in the binary tree, and this problem focuses on finding this node without simply traversing all nodes randomly.

For example, in a tree like root = [2,1,3], the leftmost value in the bottom row is 1. Similarly, with a tree root = [1,2,3,4,null,5,6,null,null,7], the bottom-left value would be 7.

Examples

Example 1

Input: root = [2,1,3]

Output: 1

Example details omitted.

Example 2

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

Output: 7

Example details omitted.

Constraints

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

Solution Approach

Breadth-First Search (BFS)

Using BFS allows you to explore the tree level by level. By visiting nodes from left to right, the last node visited at the deepest level will be the leftmost value of the last row. This ensures you always track the leftmost node for the deepest level.

Depth-First Search (DFS)

A DFS approach can be used to traverse the tree recursively, starting from the root. Keep track of the current depth and update the leftmost value whenever a deeper level is encountered, ensuring the leftmost value of the deepest row is always stored.

State Tracking During Traversal

In both BFS and DFS, maintaining state (current depth and leftmost value) is key. When traversing, if a new deepest level is found, update the stored value to the leftmost node of that level.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity is O(n), where n is the number of nodes in the binary tree, because we must visit each node once. The space complexity is also O(n) due to the storage requirements of the BFS queue or the DFS recursion stack in the worst case.

What Interviewers Usually Probe

Tests the candidate's understanding of binary tree traversal techniques.
Evaluates their ability to track state across recursive or iterative calls.
Assesses how well they handle edge cases like trees with only one node or very unbalanced trees.

Common Pitfalls or Variants

Common pitfalls

Forgetting to track the leftmost value at the deepest level, leading to an incorrect answer.
Failing to handle edge cases such as when the tree only contains one node or is unbalanced.
Using an inefficient traversal strategy that doesn't take advantage of level-order exploration.

Follow-up variants

Consider the scenario where you need to find the rightmost value of the last row instead of the leftmost.
What if the tree is a sparse binary tree with large depth?
How would the solution change if the task was to return the bottom-most value for any given row, not just the last row?

FAQ

What is the optimal solution for the Find Bottom Left Tree Value problem?

The optimal solution involves using either a BFS or DFS traversal, while tracking the leftmost node at the deepest level. BFS is typically preferred for level-order traversal.

Can DFS be used to solve the Find Bottom Left Tree Value problem?

Yes, DFS can be used by maintaining the current depth and updating the leftmost value whenever a deeper level is encountered.

What is the time complexity of the solution for the Find Bottom Left Tree Value problem?

The time complexity is O(n), where n is the number of nodes, as each node needs to be visited exactly once during traversal.

How does the bottom-left value differ from the bottom-right value in this problem?

The bottom-left value is the leftmost node at the deepest level of the tree, whereas the bottom-right value would be the rightmost node at the deepest level.

What are some common pitfalls to avoid in solving this problem?

Common pitfalls include not updating the leftmost value at the deepest level, failing to handle edge cases like a single-node tree, and using inefficient traversal strategies.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# 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:
        q = deque([root])
        ans = 0
        while q:
            ans = q[0].val
            for _ in range(len(q)):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return ans

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# 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:
        q = deque([root])
        ans = 0
        while q:
            ans = q[0].val
            for _ in range(len(q)):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return ans

Continue Practicing

#515 find largest value in each tree row #530 minimum absolute difference in bst #449 serialize and deserialize bst