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 !! :)