Wednesday 12 October 2016

Left View of a Binary Tree

Problem : Given a Binary Tree, print the left view .

Example :

Consider the following Binary Tree :


Left View of above tree : 1, 2, 4



Explanation : The left view of a given tree is nothing but the nodes that one would see when viewing the tree from the left side . For the given binary tree, the Left View shall be 1, 2, 4


Solution

There are multiple approach to solve above problem. But the basic idea is level order traversal . 
We will try to identify first node at each level and print it before moving to the next level. Trick is to identify the first element of each level. For this , we add an empty node at the end of each level. 

Implementation :

Following is the core Java implementation of approach :

 
public static void printLeftView(BinaryTreeNode root) {


    if (root == null) return;

    Queue<BinaryTreeNode> q = new LinkedList<BinaryTreeNode>();

    BinaryTreeNode flag = new BinaryTreeNode();        q.add(root);
    q.add(flag);        boolean levelover = false;
    System.out.println(root.data);
    BinaryTreeNode temp;

    //LEVEL ORDER TRAVERSAL
    while (!q.isEmpty()) {


        temp = q.remove();

        if (!temp.equals(flag) && levelover == true) {


            System.out.println(temp.data);
            levelover = false;
        }


        if (temp.equals(flag)) {


            levelover = true;
            if (!q.isEmpty()) q.add(flag);
        }


        if (temp.left != null) q.add(temp.left);
        if (temp.right != null) q.add(temp.right);

    }
}