Problem

Given a binary tree, Find the deepest left node in it.

Examples

Example 1:

1
2
3
4
5

     1
   /   \
  2     3
 /       \
4         7

1
2

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

Solution

Method 1 - Preorder Traversal

This method is similar to Find Deepest Node in a Binary Tree#Method 2 - Preorder Traversal, with modification that we pass in isLeft to the recursive calls, when going to left sub tree.

  • Take two global variable as “maxDepth” and ” deepestLeftLeaf“.
  • starting with level=0, we do the preorder traversal and whenever you go down one level ( root.left OR root.right), increase the level by 1.

Code

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

class Solution {

	private TreeNode deepestLeftLeaf = null;

	private int maxDepth = -1;

	public TreeNode findDeepestLeftLeafNode(TreeNode root) {
		dfs(root, 0, false);
		return deepestLeftLeaf;
	}

	private void dfs(TreeNode node, int depth, boolean isLeft) {
		if (node == null) {
			return;
		}
		// Check if this is a left leaf node
		if (isLeft && node.left == null && node.right == null && depth > maxDepth) {
			deepestLeftLeaf = node;
			maxDepth = depth;
		}
		// Recursively go deeper into the tree
		dfs(node.left, depth + 1, true);
		dfs(node.right, depth + 1, false);
	}
}

Method 2 - Level order traversal

To find the deepest left node:

  1. Perform a breadth-first search of the tree using a queue. This ensures we process nodes level by level.
  2. Keep track of whether the node is a left child during traversal.
  3. Update the deepest left node only if we encounter a left node deeper than the previously tracked node.

Approach

  • Step 1: Use a queue for level-wise traversal of the binary tree.
  • Step 2: For each node, check if it is a left child.
  • Step 3: Track the depth of the current node and update the result with the deepest left node found.
  • Step 4: Return the value of the deepest left node at the end.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    public Integer findDeepestLeftNode(TreeNode root) {
        if (root == null) return null; // Edge case: empty tree
        
        Queue<Pair<TreeNode, Boolean>> queue = new LinkedList<>(); // Pair of node and whether it's a left.
        queue.offer(new Pair<>(root, false));
        Integer deepestLeftValue = null;
        
        while (!queue.isEmpty()) {
            Pair<TreeNode, Boolean> current = queue.poll();
            TreeNode node = current.getKey();
            boolean isLeft = current.getValue();

            // If it's a left node, update the deepestLeftValue.
            if (isLeft) {
                deepestLeftValue = node.val;
            }

            // Add children to the queue, marking the left child correctly.
            if (node.left != null) {
                queue.offer(new Pair<>(node.left, true)); // Left child
            }
            if (node.right != null) {
                queue.offer(new Pair<>(node.right, false)); // Right child
            }
        }
        
        return deepestLeftValue;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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

    def findDeepestLeftNode(self, root):
        if not root:
            return None  # Edge case: empty tree

        from collections import deque

        queue = deque([(root, False)])  # Pair of (node, is_left)
        deepest_left_value = None

        while queue:
            node, is_left = queue.popleft()

            # If it's a left node, update the deepest_left_value.
            if is_left:
                deepest_left_value = node.val

            # Add children to the queue, marking left and right.
            if node.left:
                queue.append((node.left, True))  # Left child
            if node.right:
                queue.append((node.right, False))  # Right child

        return deepest_left_value

Complexity

  • ⏰ Time complexity: O(n) where n is the number of nodes in the binary tree (as every node is visited once).
  • 🧺 Space complexity: O(h) where h is the maximum height/depth of the binary tree (to store nodes in the queue during traversal).