LeetCode 513 - Find Bottom Left Tree Value

The problem asks us to find the leftmost value in the last row of a binary tree. A binary tree is a hierarchical data structure where each node has at most two children: a left child and a right child.

leetcodemediumtreedepth-first-searchbreadth-first-searchbinary-tree

LeetCode Problem 513

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution

Problem Understanding

The problem asks us to find the leftmost value in the last row of a binary tree. A binary tree is a hierarchical data structure where each node has at most two children: a left child and a right child. The input to the problem is the root node of the tree, which allows traversal to any other node by following child pointers. The expected output is a single integer value, representing the leftmost node of the deepest level in the tree.

Key observations include understanding that "last row" corresponds to the maximum depth of the tree. The "leftmost" node in that row is simply the first node encountered when traversing from left to right at that depth. The constraints indicate that the tree can contain up to 10,000 nodes, with node values in the signed 32-bit integer range. This size is small enough to allow standard depth-first search (DFS) or breadth-first search (BFS) traversal without hitting memory or recursion limits in Python or Go.

Important edge cases include trees with only one node, skewed trees (all left or all right children), and trees where multiple nodes exist at the deepest level. The problem guarantees at least one node exists, so no handling of empty trees is required.

Approaches

A brute-force approach would involve traversing the entire tree while keeping track of all nodes at each depth level, storing them in a list or array. Once traversal is complete, we select the first element from the last level. This works correctly but requires O(n) additional space to store all levels, which can be wasteful.

The optimal approach leverages either BFS or DFS to find the leftmost value in the last row without storing all nodes. BFS is naturally suited because it processes nodes level by level. By traversing each level from left to right and keeping track of the first node at each level, the last recorded leftmost node after BFS completes will be the correct answer. DFS can also be used by prioritizing left children before right children and keeping track of the maximum depth encountered; whenever a new maximum depth is reached, we update the result with the current node value.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Stores all nodes at all levels before selecting leftmost node at last row
BFS / DFS Optimal O(n) O(w) for BFS, O(h) for DFS BFS uses a queue of current level width w, DFS uses recursion stack up to tree height h

Algorithm Walkthrough

We will describe the BFS optimal algorithm:

  1. Initialize a queue with the root node. This queue will maintain nodes to be processed level by level.
  2. While the queue is not empty, iterate over all nodes currently in the queue (representing one level). Store the value of the first node in the level as the candidate for the leftmost value.
  3. For each node in the current level, enqueue its left child followed by its right child if they exist. This ensures the next level is processed left-to-right.
  4. After processing all nodes in the current level, repeat the process for the next level. The leftmost node of the last processed level is stored in the result.
  5. Once the queue is empty, return the stored leftmost value.

Why it works: BFS ensures nodes are processed level by level from left to right. By updating the leftmost value at the start of each level, the last stored value corresponds to the leftmost node of the deepest level.

Python Solution

# 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
from collections import deque
from typing import Optional

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        queue = deque([root])
        leftmost = root.val
        
        while queue:
            level_size = len(queue)
            for i in range(level_size):
                node = queue.popleft()
                if i == 0:
                    leftmost = node.val
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        
        return leftmost

The Python implementation initializes a double-ended queue with the root node and processes the tree level by level. At the start of each level, the first node’s value is recorded as the leftmost. Children are added to the queue in left-to-right order to preserve the BFS property. After the queue is empty, the leftmost value of the last level is returned.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findBottomLeftValue(root *TreeNode) int {
    queue := []*TreeNode{root}
    leftmost := root.Val
    
    for len(queue) > 0 {
        levelSize := len(queue)
        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            if i == 0 {
                leftmost = node.Val
            }
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    
    return leftmost
}

The Go implementation mirrors the Python BFS approach. It uses a slice as a queue, slicing off processed elements. Nil checks ensure we only enqueue valid children. The leftmost variable is updated at the start of each level to maintain the correct value.

Worked Examples

Example 1: root = [2,1,3]

Level 1: [2] → leftmost = 2

Level 2: [1,3] → leftmost = 1

Result: 1

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

Level 1: [1] → leftmost = 1

Level 2: [2,3] → leftmost = 2

Level 3: [4,5,6] → leftmost = 4

Level 4: [7] → leftmost = 7

Result: 7

Complexity Analysis

Measure Complexity Explanation
Time O(n) Every node is visited exactly once in BFS
Space O(w) Queue stores at most the maximum width w of the tree at any level

The time complexity is linear because each node is processed exactly once. The space complexity is proportional to the maximum number of nodes at any level, which is the width of the tree.

Test Cases

# test cases
assert Solution().findBottomLeftValue(TreeNode(2, TreeNode(1), TreeNode(3))) == 1  # Example 1
assert Solution().findBottomLeftValue(TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3, TreeNode(5), TreeNode(6, TreeNode(7))))) == 7  # Example 2
assert Solution().findBottomLeftValue(TreeNode(1)) == 1  # Single node
assert Solution().findBottomLeftValue(TreeNode(1, TreeNode(2))) == 2  # Left skewed
assert Solution().findBottomLeftValue(TreeNode(1, None, TreeNode(3))) == 3  # Right skewed
Test Why
[2,1,3] Verifies small complete tree
[1,2,3,4,null,5,6,null,null,7] Verifies larger tree with deep leftmost node
[1] Single node edge case
[1,2] Left skewed tree edge case
[1,null,3] Right skewed tree edge case

Edge Cases

One important edge case is a tree with only one node. Since the tree has no children, the leftmost bottom value is the root itself. Another is a left-skewed tree where each node only has a left child. Traversing level by level ensures the algorithm correctly identifies the deepest leftmost node. The third edge case is a right-skewed tree, where the algorithm still works because it tracks the first node in each level; even if a level has only right children, the first node in that level is taken as leftmost. All these cases are correctly handled by BFS updating the leftmost value at the start of each level.