Find the Deepest Left Node in a Binary Tree.

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 Treewith little modification.
  • Take two global variable as “deepestlevel” and ” deepLeftNode“.
  • starting with level=0, Do the inorder traversal and whenever you go down one level ( root.left OR root.right), increase the level by 1.
  • Keep checking if current node is the left child and deepestlevel < level, if yes then update the “deepestlevel ” and “ deepLeftNode “.
  • At the end return “ deepLeftNode “, which will the deepest node value.
  • 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;
}
}

view raw
DeepestLeftLeaf.java
hosted with ❤ by GitHub


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

view raw
DeepestLeftNode.java
hosted with ❤ by GitHub

Output:

Deapest Left child is: 18

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.