Find Bottom Left Tree Value

Given a binary tree, return the bottom-left most value.

Note: You may assume each value in the tree is unique.

Example(s)

Example 1:

Input:
      1
     / \
    2   3
   /
  4

Output: 4
Explanation:
The deepest level is level 2. The leftmost node at this level is 4.

Example 2:

Input:
      8
     / \
    1   4
       /
      2

Output: 2
Explanation:
The deepest level is level 2. The leftmost node at this level is 2.

Example 3:

Input:
      1
     / \
    2   3
   / \   \
  4   5   6
 /
7

Output: 7
Explanation:
The deepest level is level 3. The leftmost node at this level is 7.

Solution

There are two main approaches:

1. BFS (Level-order traversal): Process level by level, track the first node at each level
2. DFS (Recursive): Find the deepest level and track the leftmost node at that level

JavaScript Solution - BFS

JavaScript Solution - BFS

/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : null)
* }
*/

/**
* Find bottom-left most value using BFS
* @param {TreeNode} root - Root of the binary tree
* @return {number} - Bottom-left most value
*/
function findBottomLeftValue(root) {
if (!root) return null;

let result = root.val;
const queue = [root];

while (queue.length > 0) {
  const levelSize = queue.length;
  
  // Process all nodes at current level
  for (let i = 0; i < levelSize; i++) {
    const node = queue.shift();
    
    // First node at this level is the leftmost
    if (i === 0) {
      result = node.val;
    }
    
    // Add children to queue (left first, then right)
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
}

return result;
}

// Helper function to create TreeNode
function TreeNode(val, left, right) {
this.val = (val === undefined ? 0 : val);
this.left = (left === undefined ? null : left);
this.right = (right === undefined ? null : null);
}

// Test cases
// Example 1: [1,2,3,4]
const root1 = new TreeNode(1);
root1.left = new TreeNode(2);
root1.right = new TreeNode(3);
root1.left.left = new TreeNode(4);
console.log('Example 1:', findBottomLeftValue(root1)); // 4

// Example 2: [8,1,4,null,null,2]
const root2 = new TreeNode(8);
root2.left = new TreeNode(1);
root2.right = new TreeNode(4);
root2.right.left = new TreeNode(2);
console.log('Example 2:', findBottomLeftValue(root2)); // 2

Output:

Click "Run Code" to execute the code and see the results.

Python Solution - BFS

Python Solution - 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

from typing import Optional
from collections import deque

class TreeNode:
  def __init__(self, val=0, left=None, right=None):
      self.val = val
      self.left = left
      self.right = right

def find_bottom_left_value(root: Optional[TreeNode]) -> int:
  """
  Find bottom-left most value using BFS
  
  Args:
      root: Root of the binary tree
      
  Returns:
      int: Bottom-left most value
  """
  if not root:
      return None
  
  result = root.val
  queue = deque([root])
  
  while queue:
      level_size = len(queue)
      
      # Process all nodes at current level
      for i in range(level_size):
          node = queue.popleft()
          
          # First node at this level is the leftmost
          if i == 0:
              result = node.val
          
          # Add children to queue (left first, then right)
          if node.left:
              queue.append(node.left)
          if node.right:
              queue.append(node.right)
  
  return result

# Test cases
# Example 1: [1,2,3,4]
root1 = TreeNode(1)
root1.left = TreeNode(2)
root1.right = TreeNode(3)
root1.left.left = TreeNode(4)
print('Example 1:', find_bottom_left_value(root1))  # 4

# Example 2: [8,1,4,None,None,2]
root2 = TreeNode(8)
root2.left = TreeNode(1)
root2.right = TreeNode(4)
root2.right.left = TreeNode(2)
print('Example 2:', find_bottom_left_value(root2))  # 2

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (DFS)

Here's a DFS approach that finds the deepest level and tracks the leftmost node:

JavaScript DFS

/**
 * DFS approach
 */
function findBottomLeftValueDFS(root) {
  if (!root) return null;
  
  let maxDepth = -1;
  let result = root.val;
  
  /**
   * DFS helper
   * @param {TreeNode} node - Current node
   * @param {number} depth - Current depth
   */
  function dfs(node, depth) {
    if (!node) return;
    
    // If we found a deeper level, update result
    // Always go left first, so leftmost node at deepest level is found first
    if (depth > maxDepth) {
      maxDepth = depth;
      result = node.val;
    }
    
    // Traverse left first, then right
    // This ensures we get the leftmost node at each level
    dfs(node.left, depth + 1);
    dfs(node.right, depth + 1);
  }
  
  dfs(root, 0);
  return result;
}

Python DFS

def find_bottom_left_value_dfs(root: Optional[TreeNode]) -> int:
    """
    DFS approach
    """
    if not root:
        return None
    
    max_depth = -1
    result = root.val
    
    def dfs(node: Optional[TreeNode], depth: int):
        nonlocal max_depth, result
        
        if not node:
            return
        
        # If we found a deeper level, update result
        # Always go left first, so leftmost node at deepest level is found first
        if depth > max_depth:
            max_depth = depth
            result = node.val
        
        # Traverse left first, then right
        # This ensures we get the leftmost node at each level
        dfs(node.left, depth + 1)
        dfs(node.right, depth + 1)
    
    dfs(root, 0)
    return result

Complexity

• Time Complexity: O(n) - Where n is the number of nodes. We visit each node exactly once.
• Space Complexity:
  • BFS: O(w) - Where w is the maximum width of the tree (queue size)
  • DFS: O(h) - Where h is the height of the tree (recursion stack)

Approach

BFS Approach:

1. Level-order traversal: Process nodes level by level
2. Track first node: At each level, the first node processed is the leftmost
3. Update result: Update result with the first node at each level
4. Last level wins: The result from the last level is the answer

DFS Approach:

1. Find deepest level: Track the maximum depth encountered
2. Left-first traversal: Always traverse left subtree before right
3. Update on deeper level: When we find a deeper level, update the result
4. Leftmost guarantee: Since we go left first, the first node at the deepest level is leftmost

Key Insights

• Bottom-left: Deepest level + leftmost node at that level
• BFS naturally processes left to right: First node at each level is leftmost
• DFS with left-first: Ensures leftmost node at deepest level is found first
• Level-order is intuitive: BFS makes it easy to identify the last level
• Single pass: Both approaches visit each node once

Step-by-Step Example

Let's trace through Example 1: root = [1,2,3,4]

Tree:
      1
     / \
    2   3
   /
  4

BFS Approach:
Level 0: [1]
  Process node 1: result = 1 (first node at level 0)
  Queue: [2, 3]

Level 1: [2, 3]
  Process node 2: result = 2 (first node at level 1)
  Process node 3: (not first, skip)
  Queue: [4]

Level 2: [4]
  Process node 4: result = 4 (first node at level 2)
  Queue: []

Final: result = 4

DFS Approach (left-first):
dfs(1, depth=0):
  depth=0 > maxDepth=-1 → update: maxDepth=0, result=1
  dfs(2, depth=1):
    depth=1 > maxDepth=0 → update: maxDepth=1, result=2
    dfs(4, depth=2):
      depth=2 > maxDepth=1 → update: maxDepth=2, result=4
      dfs(null, depth=3) → return
      dfs(null, depth=3) → return
    dfs(null, depth=2) → return
  dfs(3, depth=1):
    depth=1 not > maxDepth=2 → skip
    dfs(null, depth=2) → return
    dfs(null, depth=2) → return

Final: result = 4

Visual Representation

Example 1:
      1          Level 0: [1] → leftmost = 1
     / \
    2   3        Level 1: [2, 3] → leftmost = 2
   /
  4              Level 2: [4] → leftmost = 4 ✓

Example 2:
      8          Level 0: [8] → leftmost = 8
     / \
    1   4        Level 1: [1, 4] → leftmost = 1
       /
      2          Level 2: [2] → leftmost = 2 ✓

Edge Cases

• Single node: Return the root value
• Left-skewed tree: Return the leftmost leaf
• Right-skewed tree: Return the leftmost node at deepest level (might be right child)
• Perfect tree: Return the leftmost leaf
• Empty tree: Return null (if allowed)

Important Notes

• Bottom-left: Deepest level + leftmost position
• Leftmost at deepest level: Not necessarily the leftmost overall
• BFS processes left to right: Natural ordering helps
• DFS left-first: Ensures leftmost node found first at each depth
• Unique values: Problem guarantees unique values

BFS vs DFS

Approach	Time	Space	Pros	Cons
BFS	O(n)	O(w)	Intuitive, level-by-level	More space for wide trees
DFS	O(n)	O(h)	Less space for deep trees	Slightly more complex logic

Related Problems

• Maximum Depth of Binary Tree: Find the deepest level
• Binary Tree Level Order Traversal: Similar BFS approach
• Find Largest Value in Each Tree Row: Different but related
• Right Side View of Binary Tree: Opposite problem

Takeaways

• BFS naturally processes levels left to right
• First node at last level is the bottom-left value
• DFS with left-first also works efficiently
• O(n) time is optimal (must visit all nodes)
• Level-order traversal is the most intuitive approach