Print Left View of a given binary tree

by

Objective: In a Binary Tree, print left view of it

Input: A binary tree.

What is left View of a binary Tree

When just look at the tree from the left side , all the nodes you can see will be the left view of the tree.

Example:

Left View of a binary tree

Approach:

Method 1:

  • Traverse the tree from left to right
  • Print the first node you encounter
  • Take two variables , currentLevel=0 and nextLevel=1
  • As soon as you change level , change the currentLevel = nextLevel
  • Print only when current level<nextLevel so this way you will print only the first element
  • For rest of the nodes on the the level currentLevel and nextLevel are equal so it wont print

Method 2:

Do the Level order traversal and print the first node value

Complete Code:

public class LeftViewOfTree {
public static int index = 0;
public void Method2_levelOrder(Node root) {
int h = height(root);
for (int i = 1; i <= h; i++) {
index = 1;
printLevels(root, i);
// System.out.println("");
}
}
public void printLevels(Node root, int h) {
if (root == null)
return;
if (h == 1 && index == 1) {
System.out.print(" " + root.data);
index++;
} else {
printLevels(root.left, h – 1);
printLevels(root.right, h – 1);
}
}
public static int currentLevel =0;
public void leftViewRecur(Node root, int nextLevel){
if(root==null) return;
if(currentLevel<nextLevel){
System.out.print (" " + root.data);
currentLevel = nextLevel;
}
leftViewRecur(root.left,nextLevel+1);
leftViewRecur(root.right,nextLevel+1);
}
public int height(Node root) {
if (root == null)
return 0;
return 1 + Math.max(height(root.left), height(root.right));
}
public static void main(String[] args) throws java.lang.Exception {
Node root = new Node(5);
root.left = new Node(10);
root.right = new Node(15);
root.left.left = new Node(20);
root.left.right = new Node(25);
root.right.left = new Node(30);
root.right.right = new Node(35);
root.left.right.right = new Node(45);
LeftViewOfTree i = new LeftViewOfTree();
System.out.println("METHOD 1: ");
i.leftViewRecur(root, 1);
System.out.println("\nMETHOD 2 : Using Level Order, Left view ");
i.Method2_levelOrder(root);
}
}
class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}

view raw
LeftViewOfTree.java
hosted with ❤ by GitHub

Output:

METHOD 1:
5 10 20 45
METHOD 2 : Using Level Order, Left view
5 10 20 45

Related Posts: