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

    }

}

Least Common Ancestor : Binary Tree

Lowest Common Ancestor:

In graph theory and computer science, the lowest common ancestor (LCA) of two nodes v and w in a tree or directed acyclic graph (DAG) T is the lowest (i.e. deepest) node that has both v and w as descendants, where we define each node to be a descendant of itself (so if v has a direct connection from w, w is the lowest common ancestor).

The LCA of v and w in T is the shared ancestor of v and w that is located farthest from the root. Computation of lowest common ancestors may be useful, for instance, as part of a procedure for determining the distance between pairs of nodes in a tree: the distance from v to w can be computed as the distance from the root to v, plus the distance from the root to w, minus twice the distance from the root to their lowest common ancestor (Djidjev, Pantziou & Zaroliagis 1991). In ontologies, the lowest common ancestor is also known as the least common subsumer.

In a tree data structure where each node points to its parent, the lowest common ancestor can be easily determined by finding the first intersection of the paths from vand w to the root. In general, the computational time required for this algorithm is O(h) where h is the height of the tree (length of longest path from a leaf to the root). However, there exist several algorithms for processing trees so that lowest common ancestors may be found more quickly. Tarjan's off-line lowest common ancestors algorithm, for example, preprocesses a tree in linear time to provide constant-time LCA queries. In general DAGs, similar algorithms exist, but with super-linear complexity.

[SOURCE: https://en.wikipedia.org/wiki/Lowest_common_ancestor]

Problem :

Given a binary tree and two values d1& d2, find the least common ancestor of the two values in the input tree.


Example:
  Consider the following image :

Solution :
We follow a recursive approach where in we recurse through the right and left children of the parameter node .

Return value is root itself if output of each recursion is null , else the we return the value is which in non-null among the two recursive output.

Base and Edge cases are as shown in the code.

Implementation:

Binary Tree Node :

public class BinaryTreeNode {

    private int data;    private BinaryTreeNode left;    private BinaryTreeNode right;
    public int getData() {
        return data;    }

    public void setData(int data) {
        this.data = data;    }

    public BinaryTreeNode getLeft() {
        return left;    }

    public void setLeft(BinaryTreeNode left) {
        this.left = left;    }

    public BinaryTreeNode getRight() {
        return right;    }

    public void setRight(BinaryTreeNode right) {
        this.right = right;    }
}

LCA class : 

public class LCA {


    public BinaryTreeNode getLCA(BinaryTreeNode root, int data1, int data2){

    //Base case
        if (root == null){
            return  null;        }

    //edge case
        if (root.getData()==data1 || root.getData() == data2) {
            return root;        }


    BinaryTreeNode leftLCA = getLCA(root.getLeft(), data1, data2);            BinaryTreeNode rightLCA = getLCA(root.getRight(), data1, data2);

    if (leftLCA != null && rightLCA != null){
        return root;    }

    if (leftLCA == null) {
        return rightLCA;    }

    else {
        return leftLCA;    }


    }
}

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==>