1.

Print Left view of any binary trees.

Answer»

  • The main idea to solve this problem is to traverse the tree in pre order manner and pass the level information along with it. If the level is visited for the first time, then we store the information of the current node and the current level in the hashmap. Basically, we are getting the left view by noting the first node of every level.

  • At the end of traversal, we can get the solution by just traversing the map.

  • Consider the following tree as example for finding the left view:

  • Left view of a binary tree in Java:

import java.util.HashMap;

//to store a Binary Tree node
class Node
{
int data;
Node left = null, right = null;

Node(int data) {
this.data = data;
}
}
public class InterviewBit
{
// traverse nodes in pre-order way
public static void leftViewUtil(Node root, int level, HashMap<Integer, Integer> map)
{
if (root == null) {
return;
}

// if you are visiting the level for the first time
// insert the current node and level info to the map
if (!map.containsKey(level)) {
map.put(level, root.data);
}

leftViewUtil(root.left, level + 1, map);
leftViewUtil(root.right, level + 1, map);
}

// to print left view of binary tree
public static void leftView(Node root)
{
// create an empty HashMap to store first node of each level
HashMap<Integer, Integer> map = new HashMap<>();

// traverse the tree and find out the first nodes of each level
leftViewUtil(root, 1, map);

// iterate through the HashMap and print the left view
for (int i = 0; i <map.size(); i++) {
System.out.print(map.get(i) + " ");
}
}

public static void main(String[] args)
{
Node root = new Node(4);
root.left = new Node(2);
root.right = new Node(6);
root.left.left = new Node(1);
root.left.left = new Node(3);
root.right.left = new Node(5);
root.right.right = new Node(7);
root.right.left.left = new Node(9);

leftView(root);
}
}


Discussion

No Comment Found

Related InterviewSolutions