**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:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

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.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

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