Left view of tree means - nodes which are visible when tree is viewed from left side.And similarly right view of tree is all nodes visible from right side of tree.Consider following binary tree
Left view of tree : [12,23,11,56]
Approach 1:- Using level order traversal
Traverse binary tree in level order and maintain a queue indicating start of node at each level. Here I have used
Integer.MAX_VALUE as marker indicating start of new level.
Algorithm:-
1. Insert root and marker in queue, display root as it will be visible from left side.
2. Loop queue until it is empty
2.1 Remove element from queue and check it is marker. If marker and queue is not empty(last
marker of tree) set flag true to display next element from queue.
2.2 If removed node has left and right child, insert them in queue. Left followed by right child.
2.3 If flag is set, display removed element and flip flag status
Note:- We are checking queue is empty or not in step 2.1 because when last marker is removed and queue become empty, we do not need to put marker again assuming next level will start.
Sample code:-
public static void leftViewOfTree(Node root) {
if (root == null)
return;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
boolean leftFlag = false;
queue.add(new Node(Integer.MAX_VALUE));
System.out.println(root.getData() + " ");
while (!queue.isEmpty()) {
Node temp = queue.remove();
if (leftFlag && !queue.isEmpty()) {
System.out.println(temp.getData());
leftFlag = false;
}
if (temp.getData() == Integer.MAX_VALUE && !queue.isEmpty()) {
queue.add(new Node(Integer.MAX_VALUE));
leftFlag = true;
}
if (temp != null) {
if (temp.getLeftChild() != null) {
queue.add(temp.getLeftChild());
}
if (temp.getRightChild() != null) {
queue.add(temp.getRightChild());
}
}
}
}
Approach 2:- Recursive traversal and using a mapHere we traverse binary tree assuming root at level 0 and maintain a
linked Hashmap for storing first node of that level.
Algorithm:-
1. Insert root node in map with key as 0 and node as value.
2. For each node we traverse - mark left child level as currentLevel -1 and for right child as currentLevel -1.
3. Make an entry in map with level value as key, if it already does not exist and traverse recursively left child followed by right child.
Sample code:-
public static void leftViewRecur(Node root) {
Map<Integer, Node> map = new LinkedHashMap<>();
map.put(0, root);
leftViewRecurUtil(root, 0, map);
for (Node temp : map.values()) {
System.out.println(temp.getData());
}
}
private static void leftViewRecurUtil(Node root, int level,
Map<Integer, Node> map) {
if (root == null)
return;
if (root.getLeftChild() != null) {
if (map.get(level + 1) == null) {
map.put(level + 1, root.getLeftChild());
}
leftViewRecurUtil(root.getLeftChild(), level + 1, map);
}
if (root.getRightChild() != null) {
if (map.get(level + 1) == null) {
map.put(level + 1, root.getRightChild());
}
leftViewRecurUtil(root.getRightChild(), level + 1, map);
}
}
Approach 3:- Recursive traversal and using a mapIt is similar to above approach but here we are not maintaining map for storing first node of the given level, we maintain a global variable
maxLevel - which indicates current max level reached and for left and right child level is passed as currentLevel + 1.
Algorithm:-
1. Iterate tree recursively left subtree followed by right subtree and pass level as currentLevel+1 .
2. Compare maxLevel with current level
if maxLevel < levelOfNode , print it as left view node
Sample code:-
public static void leftViewRecurWithLevel(Node root, int level) {
if (root == null)
return;
if (maxLevel < level) {
System.out.println(root.getData());
maxLevel = level;
}
if (root.getLeftChild() != null) {
leftViewRecurWithLevel(root.getLeftChild(), level + 1);
}
if (root.getRightChild() != null) {
leftViewRecurWithLevel(root.getRightChild(), level + 1);
}
}
Complete sample program with all 3 approaches :-
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
public class LeftViewOfTree {
/**
* devinline.com
*
*/
static private int maxLevel = 0;
public static void leftViewOfTree(Node root) {
if (root == null)
return;
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
boolean leftFlag = false;
queue.add(new Node(Integer.MAX_VALUE));
System.out.println(root.getData() + " ");
while (!queue.isEmpty()) {
Node temp = queue.remove();
if (leftFlag && !queue.isEmpty()) {
System.out.println(temp.getData());
leftFlag = false;
}
if (temp.getData() == Integer.MAX_VALUE && !queue.isEmpty()) {
queue.add(new Node(Integer.MAX_VALUE));
leftFlag = true;
}
if (temp != null) {
if (temp.getLeftChild() != null) {
queue.add(temp.getLeftChild());
}
if (temp.getRightChild() != null) {
queue.add(temp.getRightChild());
}
}
}
}
public static void leftViewRecur(Node root) {
Map<Integer, Node> map = new LinkedHashMap<Integer, Node>();
map.put(0, root);
leftViewRecurUtil(root, 0, map);
for (Node temp : map.values()) {
System.out.println(temp.getData());
}
}
private static void leftViewRecurUtil(Node root, int level,
Map<Integer, Node> map) {
if (root == null)
return;
if (root.getLeftChild() != null) {
if (map.get(level + 1) == null) {
map.put(level + 1, root.getLeftChild());
}
leftViewRecurUtil(root.getLeftChild(), level + 1, map);
}
if (root.getRightChild() != null) {
if (map.get(level + 1) == null) {
map.put(level + 1, root.getRightChild());
}
leftViewRecurUtil(root.getRightChild(), level + 1, map);
}
}
public static void leftViewRecurWithLevel(Node root, int level) {
if (root == null)
return;
if (maxLevel < level) {
System.out.println(root.getData());
maxLevel = level;
}
if (root.getLeftChild() != null) {
leftViewRecurWithLevel(root.getLeftChild(), level + 1);
}
if (root.getRightChild() != null) {
leftViewRecurWithLevel(root.getRightChild(), level + 1);
}
}
public static void rightViewRecur(Node root, int level) {
if (root == null)
return;
if (maxLevel < level) {
System.out.println(root.getData());
maxLevel = level;
}
if (root.getRightChild() != null) {
rightViewRecur(root.getRightChild(), level + 1);
}
if (root.getLeftChild() != null) {
rightViewRecur(root.getLeftChild(), level + 1);
}
}
public static void main(String[] args) {
java.util.Scanner scanner = new java.util.Scanner(System.in);
System.out.println("Enter input between (1 to 3)");
int input = scanner.nextInt();
BinaryTree bt = new BinaryTree();
Node root = bt.createTree();
switch (input) {
case 1:
leftViewOfTree(root);
break;
case 2:
leftViewRecur(root);
break;
case 3:
leftViewRecurWithLevel(root, 1);
break;
default:
break;
}
}
}
class BinaryTree {
Node root;
public BinaryTree() {
root = null;
}
public Node createTree() {
if (root == null) {
root = new Node(12);
}
root.setLeftChild(new Node(23));
root.setRightChild(new Node(18));
root.getLeftChild().setLeftChild(new Node(11));
root.getLeftChild().setRightChild(new Node(43));
root.getRightChild().setLeftChild(new Node(12));
root.getLeftChild().getLeftChild().setLeftChild(new Node(56));
root.getLeftChild().getLeftChild().setRightChild(new Node(78));
root.getRightChild().getLeftChild().setRightChild(new Node(98));
root.getRightChild().setRightChild(new Node(99));
return root;
}
}
class Node {
private int data;
private Node leftChild;
private Node rightChild;
public Node(int data) {
this.data = data;
leftChild = null;
rightChild = null;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getLeftChild() {
return leftChild;
}
public void setLeftChild(Node leftChild) {
this.leftChild = leftChild;
}
public Node getRightChild() {
return rightChild;
}
public void setRightChild(Node rightChild) {
this.rightChild = rightChild;
}
}
Sample output:-
====================
>java LeftViewOfTree
Enter input between (1 to 3)
1
12
23
11
56
>java LeftViewOfTree
Enter input between (1 to 3)
2
12
23
11
56
>java LeftViewOfTree
Enter input between (1 to 3)
3
12
23
11
56
====================
