Problem

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

Examples

Example 1:

graph TD
	A(2)
	A(2) --- B(1):::leftMost
	A(2) --- C(3)

classDef leftMost fill:#3CB371,stroke:#000,stroke-width:1px,color:#fff; 
  
1
2

Input: root = [2,1,3]
Output: 1

Example 2:

graph TD
    A(1)
    A(1) --- B(2)
    A(1) --- C(3)
    B(2) --- D(4):::leftMost
    B ~~~ N1:::hidden
    C(3) --- E(5)
    C(3) --- F(6)
    E(5) --- G(7):::leftMost
    E ~~~ N2:::hidden

classDef leftMost fill:#3CB371,stroke:#000,stroke-width:1px,color:#fff;
classDef hidden display:none
  
1
2

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

Solution

Understanding the problem. WE can’t just go left and elft and find the answer. We can also have the answer in right part of the root. So, idea is to get the leftmost value in the last row. That implies doing level order traversal.

Method 1 - Level Order Traversal - Left to Right

We will use Breadth-First Search (BFS) using a queue to traverse the tree level by level and ensure we capture the leftmost value at the last row. Here’s the approach:

  1. Initialisation: Start the BFS traversal with the root node in the queue.
  2. Update Row: At each level, iterate through all nodes in the current level of the queue. Keep track of the leftmost node at that level.
  3. Leftmost Tracking: For each level, ensure the value stored corresponds to the first node in the level.
  4. Continue Traversal: Add the left and right children of each node into the queue to enable processing of the next level.
  5. Result: The last updated leftmost value is the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        int ans = 0; // Result variable for the leftmost value
        Queue<TreeNode> queue = new LinkedList<>(); // BFS queue
        queue.add(root); // Start BFS from root

        while (!queue.isEmpty()) {
            int size = queue.size(); // Number of nodes at the current level
            ans = queue.peek().val; // Leftmost value in the current level

            for (int i = 0; i < size; i++) {
                TreeNode curr = queue.poll(); // Remove current node from the queue
                // Add children to the queue for the next level
                if (curr.left != null) queue.add(curr.left);
                if (curr.right != null) queue.add(curr.right);
            }
        }

        return ans; // The leftmost value at the last row
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        ans: int = 0  # Result variable
        queue: deque[TreeNode] = deque([root])  # BFS queue starting with root
        
        while queue:
            size: int = len(queue)  # Number of nodes at current level
            ans = queue[0].val  # Leftmost value in the current level
            
            for _ in range(size):
                curr: Optional[TreeNode] = queue.popleft()  # Remove current node from the queue
                # Add children to the queue for next level
                if curr.left:
                    queue.append(curr.left)
                if curr.right:
                    queue.append(curr.right)
        
        return ans  # The leftmost value at the last row

Complexity

  • ⏰ Time complexity: O(n), where n is the number of nodes in the binary tree, as this algorithm visits each node exactly once.
  • 🧺 Space complexity: O(n).
    • The queue stores nodes at most one full level of the tree at a time.
    • In the worst case (balanced binary tree), the last row may have n/2 nodes.

Method 2 - BFS - Right to Left

By traversing nodes right to left, we ensure that the last node processed at the deepest level during BFS is the leftmost node. Therefore, there’s no need to track the first element added; the last value in the traversal is the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
	public int findBottomLeftValue(TreeNode root) {
	    Queue<TreeNode> queue = new LinkedList<>();
	    queue.add(root);
	    while (!queue.isEmpty()) {
	        root = queue.poll();
	        if (root.right != null)
	            queue.add(root.right);
	        if (root.left != null)
	            queue.add(root.left);
	    }
	    return root.val;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class TreeNode:
    def __init__(self, val: int = 0, left: Optional['TreeNode'] = None, right: Optional['TreeNode'] = None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        queue = deque([root])
        
        while queue:
            root = queue.popleft()
            # Add right child first, then left child for right-to-left traversal
            if root.right:
                queue.append(root.right)
            if root.left:
                queue.append(root.left)
        
        return root.val

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Method 3 - DFS

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
	public int findBottomLeftValue(TreeNode root) {
		return findBottomLeftValue(root, 1, new int[]{0,0});
	}
	public int findBottomLeftValue(TreeNode root, int depth, int[] res) {
		if (res[1]<depth) {
			res[0]=root.val;
			res[1]=depth;
		}
		if (root.left!=null) {
			findBottomLeftValue(root.left, depth+1, res);
		}
		if (root.right!=null) {
			findBottomLeftValue(root.right, depth+1, res);
		}
		return res[0];
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        res = [0, 0]  # res[0] = value of leftmost node, res[1] = max depth
        return self._findBottomLeftValue(root, 1, res)
    
    def _findBottomLeftValue(self, root: Optional[TreeNode], depth: int, res: list[int]) -> int:
        if res[1] < depth:
            res[0] = root.val
            res[1] = depth
        
        if root.left:
            self._findBottomLeftValue(root.left, depth + 1, res)
        if root.right:
            self._findBottomLeftValue(root.right, depth + 1, res)
        
        return res[0]

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(h)