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);

    }

}

Height of a Binary tree : Recursive and Iterative Approach

Problem : Given a Binary Tree , find the height of the tree. 

 Example:

Height of above Tree = 3

Explanation:

 Height of a binary tree is  the number of nodes along the longest path from the root node down to the farthest leaf node. The Height of the empty tree is 0, the Height of the tree in the above example is 3

Solution : 

There can be two approach to solve this problem : 

1. Recursive : using recursive calls to find heights of left and right subtress 

2. Iterative : using level order traversal 

Let us have a look at both the approaches one by one : 

A. Recursive Solution :  

   1. if the root ==null , return 0

Else : perform 2 -->4

   2. find height of left subtree , say LH 

   3. find height of right subtree , say RH

   4. if LH >RH, return LH +1 , else return RH+1

B. Iterative Solution :

 Do a level order traversal, increment height at each level. Return height at the end.

Implementation : 

Following are the java implementations for both solutions 

A. RECURSIVE :

 int height(Node root){

        

         if(root==null) return 0;

       

       else{

            int lh= height(root.left);

            int rh= height(root.right);

       

       if(lh>rh) return lh+1;

       else return rh+1;

       }

          

    }

B. ITERATIVE :

 int height(Node root)

    {

         if(root==null) return 0;

       Node node=root;

       int height=0;

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

       q.add(node);

       

       while(true){

            // nodeCount (queue size) indicates number of nodes

            // at current lelvel.

            int nodeCount = q.size();

            if (nodeCount == 0) {

                return height;

            }

            height++;

            // Dequeue all nodes of current level and Enqueue all

            // nodes of next level

            while (nodeCount > 0) {

                Node newnode = q.peek();

                q.remove();

                if (newnode.left != null) {

                    q.add(newnode.left);

                }

                if (newnode.right != null) {

                    q.add(newnode.right);

                }

                nodeCount--;

            }

        }

           

           

           

       }

    

________________________________________________________________________________

REFERENCES : 

http://cslibrary.stanford.edu/110/BinaryTrees.html

https://www.hackerrank.com/challenges/tree-height-of-a-binary-tree

Graph Theory : Breadth First Search

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key) and explores the neighbour nodes first, before moving to the next level neighbour.

BFS was invented in the late 1950s by E. F. Moore, who used it to find the shortest path out of a maze, and discovered independently by C. Y. Lee as a wire routing algorithm (published 1961).

[Source :https://en.wikipedia.org/wiki/Breadth-first_search ]

BFS of above tree would give : 1 -->2-->3-->4-->5-->6-->7-->8-->9-->10-->11-->12

Solution : 

In order to implement BFS , we use a queue data structure (Similar to level order traversal of a tree). We also maintain a boolean array to mark all the visited nodes with value='true'

We start with root , and add it to queue. 

Now we iterate through the queue as follows , until the queue is empty and do following :

• fetch a node from q,
• print it
• fetch all its adjacent nodes, mark them visited and add them in queue

Implementation :

// 1. Graph Class : 

import java.util.Iterator;

import java.util.LinkedList;

import java.util.List;

class Graph {

private int v; // no of vertices in the graph
List<Integer> adj[]; // adjacency list

public Graph(int v) {

this.v = v;
adj = new ArrayList[v];

for (int i = 0; i < v; i++)
adj[i] = new ArrayList<Integer>();
}

public int getV() {
return v;
}

public void setV(int v) {
this.v = v;
}

public List<Integer>[] getAdj() {
return adj;
}

public void setAdj(List<Integer>[] adj) {
this.adj = adj;
}

public void addEdge(int v, int w) {
this.adj[v].add(w);
}

}

// 2. BFS CLASS 

class BFS {



public void printBFS(int v, Graph g) {

// mark all vertices as non visited

boolean visited[] = new boolean[g.getV()];
LinkedList<Integer> q= new LinkedList<Integer>();


visited[v]=true;
q.add(v);



while (!q.isEmpty()) {

v = q.poll();
System.out.print(v+"==>");

Iterator<Integer> it = g.adj[v].iterator();
while(it.hasNext()){
int n = it.next();
               if (!visited[n])
               {
                   visited[n] = true;
                   q.add(n);
               }


}
}


}


}


//TESTER CLASS : 

public class GraphTester {

    public static void main(String args[]){

        Graph g=new Graph(4);
        g.addEdge(0,1);
        g.addEdge(0, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(1, 2);
        g.addEdge(3, 3);



        BFS bfs= new BFS();
        System.out.println("BREADTH FIRST SEARCH TRAVERSAL OF INPUT GRAPH ");

        bfs.printBFS(2, g);
}

}


****************************************************************************

OUTPUT :

BREADTH FIRST SEARCH TRAVERSAL OF INPUT GRAPH 

2==>0==>3==>1==>