**Objective: –** Given a binary tree, Find the deepest left node in it.

**Approach: **

- This approach is very similar to “
**Find the Deepest Node in a Binary Tree”**with little modification. - Take two global variable as “
” and ”*deepestlevel*“.*deepLeftNode* - starting with
=0, Do the inorder traversal and whenever you go down one level ( root.left OR root.right), increase the level by 1.*level* - Keep checking if current node is the
and*left child*, if yes then update the “*deepestlevel < level*” and “*deepestlevel*“.*deepLeftNode* - At the end return “
“, which will the deepest node value.*deepLeftNode* - See the code for better explanation.

**Code:**

public class DeepestLeftLeaf { | |

public int deepestLevel = 0; | |

public int deepLeftNode; | |

public int deepLeft(Node root) { | |

find(root, 0, true); | |

return deepLeftNode; | |

} | |

public void find(Node root, int level, boolean left) { | |

if (root != null) { | |

find(root.left, ++level, true); | |

if (left && deepestLevel < level) {// check if it a left child and | |

// current level is greater than deepest level | |

deepLeftNode = root.data; // update the deepest left node | |

deepestLevel = level; // update the deepest level | |

} | |

find(root.right, level, false); | |

} | |

} | |

public static void main(String args[]) { | |

Node root = new Node(1); | |

root.left = new Node(2); | |

root.right = new Node(3); | |

root.left.left = new Node(4); | |

root.left.right = new Node(5); | |

root.left.left.right = new Node(8); | |

DeepestLeftLeaf dp = new DeepestLeftLeaf(); | |

System.out.println("Deapest Left child is: " + dp.deepLeft(root)); | |

} | |

} | |

class Node { | |

int data; | |

Node left; | |

Node right; | |

public Node(int data) { | |

this.data = data; | |

this.left = null; | |

this.right = null; | |

} | |

} |

**Output**:

Deapest Left child is: 4

**Approach: ** – Without using global variables

We will keep track of the deepest left node and pass it along during recursion. Will take the Result object ( with data and level). See the code below for more understanding.

public class DeepestLeftNode { | |

public Result deepLeft(Node root, boolean isLeft, int level){ | |

if(root==null) | |

return null; | |

Result left = deepLeft(root.left, true, level+1); | |

Result right = deepLeft(root.right, false, level+1); | |

Result result = null; | |

if(left!=null){ | |

result = left; | |

} | |

if(right!=null){ | |

if(result==null) | |

result = right; | |

else if(result.level<right.level) { | |

result = right; | |

} | |

} | |

//if both left and right are null | |

if(result==null && isLeft){ | |

return new Result(level, root); | |

} | |

return result; | |

} | |

public static void main(String[] args) { | |

Node root = new Node(1); | |

root.left = new Node(2); | |

root.right = new Node(3); | |

root.left.left = new Node(4); | |

root.left.right = new Node(5); | |

root.left.left.right = new Node(8); | |

root.left.left.right.left = new Node(18); | |

DeepestLeftNode dp = new DeepestLeftNode(); | |

System.out.println("Deapest Left child is: " + dp.deepLeft(root, false, 0).node.data); | |

} | |

static class Result{ | |

int level; | |

Node node; | |

public Result(int level, Node node) { | |

this.level = level; | |

this.node = node; | |

} | |

} | |

static class Node{ | |

int data; | |

Node left; | |

Node right; | |

public Node(int data) { | |

this.data = data; | |

} | |

} | |

} |

**Output**:

Deapest Left child is: 18