Problem

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

Examples

Example 1:

     1
   /   \
  2     3
 /       \
4         7

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

Java
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);
	}
}