22 Oct 2013

Left View of Binary Tree

Problem Statement :
             Print Left View of Binary Tree.
Fig: Given Binary Tree
Solution : 

Those who have worked out Level order traversal , the first solution comes in mind is to print the first node at each level but with recursion how will i stop the unwinding stack to print other nodes.

The Problem can also be solved using Queue.

The Left view of the above Binary Tree is shown below , with blue colored nodes:


Fig : Left view with( blue nodes)


I will be discussing two approaches for solving this problem :

1.  Using Recursion 
The concept: 
          Once a max Level is reached all the nodes lower than the max level will not be printed while stack is unwinding , hence we will keep a static variable keeping track of the max Level. We will proceed by printing left sub-tree first of each node. Initially max Level will chase 'level' variable.

Refer to Full Source Code here


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
public void leftView(Node root, int level )
 {
  if(root==null)
   return;
  
  if(maxLevel < level)  {
   System.out.println(root.data);
   maxLevel = level;
  }
 
  leftView(root.left, level+1 );
  leftView(root.right, level + 1 );
 }


2. Using Queue

The Concept:
       Algorithm:

  1. Insert Root , insert null
  2. dequeue until Queue is empty
  3. dequeue item
              a) If dequeued item is null
                         set flag , (the next item poped is to be printed)
             b) If dequeue item is not null ,
                         enqueue its left and right child
    4. If flag is set Print the item and set flag to false.

Queue that will be formed for the above Tree:


1
NULL
2
3
NULL
4
5
6
7
NULL
8
NULL
9
NULL
10
NULL


Please refer to Source Code here


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public void leftViewQueue(Node root) {

  boolean isFirstNode = false;
  LinkedList<Node> queue = new LinkedList<Node>();

  queue.addLast(root);  //enqueue
  queue.addLast(null);  //enqueue

  System.out.print(root.data + "\t");
  while (!queue.isEmpty()) {
   Node poped = queue.removeFirst(); //dequeue  

   if (poped == null) {     
    isFirstNode = true;  //current level processed , push null for next level
    queue.addLast(null);
   } 
   else {
    
    if(isFirstNode == true)
    {
     System.out.print(poped.data + "\t");  // Print first Node 
        isFirstNode = false;       //and set flag to be false until next null encountered
    }
    
    if (poped.left != null)
    queue.addLast(poped.left);
    if (poped.right != null)
    queue.addLast(poped.right);
   }
  }
 }

Hope the post is useful , please post comments , suggestions or any code optimisation.

Happy Coding !! :)


No comments:

Post a Comment