LCA in BinaryTree

 For any node r, we know the following:
1.       If p is on one side and q is on the other, r is the first common ancestor.
2.       Else, the first common ancestor is on the left or the right side.
So, we can create a simple recursive algorithm called search that calls search(left side) and search(right side) looking at how many nodes (p or q) are placed from the left side and from the right side of the current node. If there are two nodes on one of the sides, then we have  to check if the child node on this side is p or q (because in this case the current node is the common ancestor). If the child node is neither p nor q, we should continue to search further
(starting from the child).

If one of the searched nodes (p or q) is located on the right side of the current node, thenthe other node is located on the other side. Thus the current node is the common ancestor.

1       static int TWO_NODES_FOUND = 2;
2       static int ONE_NODE_FOUND = 1;
3       static int NO_NODES_FOUND = 0;
4              
5       // Checks how many “special” nodes are located under this root
6       int covers(TreeNode root, TreeNode p, TreeNode q) {
7                int ret = NO_NODES_FOUND;
8                if (root == null) return ret;
9                if (root == p || root == q) ret += 1;
10               ret += covers(root.left, p, q);
11               if(ret == TWO_NODES_FOUND) // Found p and q
12                      return ret;
13               return ret + covers(root.right, p, q);
14      }
15             
16      TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q) {
17               if (q == p && (root.left == q || root.right == q)) return root;
18               int nodesFromLeft = covers(root.left, p, q); // Check left side
19               if (nodesFromLeft == TWO_NODES_FOUND) {
20                      if(root.left == p || root.left == q) return root.left;
21                      else return commonAncestor(root.left, p, q);
22               } else if (nodesFromLeft == ONE_NODE_FOUND) {
23                      if (root == p) return p;
24                      else if (root == q) return q;
25               }
26               int nodesFromRight = covers(root.right, p, q); // Check right side
27               if(nodesFromRight == TWO_NODES_FOUND) {
28                      if(root.right == p || root.right == q) return root.right;
29                      else return commonAncestor(root.right, p, q);
30               } else if (nodesFromRight == ONE_NODE_FOUND) {
31                      if (root == p) return p;
32                      else if (root == q) return q;
33               }
34               if (nodesFromLeft == ONE_NODE_FOUND &&
35                      nodesFromRight == ONE_NODE_FOUND) return root;
36               else return null;
37      }

Write an algorithm to find the ‘next’ node (e.g., in-order successor) of a given node in a binary search tree where each node has a link to its parent.

We approach this problem by thinking very, very carefully about what happens on an in-order traversal. On an in-order traversal, we visit X.left, then X, then X.right.So, if we want to find X.successor(), we do the following:
1. If X has a right child, then the successor must be on the right side of X (because of the
order in which we visit nodes). Specifically, the left-most child must be the first node visited
in that subtree.
2. Else, we go to X’s parent (call it P).
2.a. If X was a left child (P.left = X), then P is the successor of X
2.b. If X was a right child (P.right = X), then we have fully visited P, so we call successor(P).   

1        public static TreeNode inorderSucc(TreeNode e) {
2                if (e != null) {
3                         TreeNode p;
4                         // Found right children -> return 1st inorder node on right
5                         if (e.parent == null || e.right != null) {
6                                  p = leftMostChild(e.right);
7                         } else {
8                                  // Go up until we’re on left instead of right (case 2b)
9                                  while ((p = e.parent) != null) {
10                                          if (p.left == e) {
11                                                   break;
12                                          }
13                                          e = p;
14                                 }
15                        }
16                        return p;
17               }
18               return null;
19       }
20              
21       public static TreeNode leftMostChild(TreeNode e) {
22               if (e == null) return null;
23               while (e.left != null) e = e.left;
24               return e;
25       }

Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height.

Algorithm:
1.     Insert into the tree the middle element of the array.
2.     Insert (into the left subtree) the left subarray elements
3.     Insert (into the right subtree) the right subarray elements
4.     Recurse


1      public static TreeNode addToTree(int arr[], int start, int end){
2              if (end < start) {
3                       return null;
4              }
5              int mid = (start + end) / 2;
6              TreeNode n = new TreeNode(arr[mid]);
7              n.left = addToTree(arr, start, mid - 1);
8              n.right = addToTree(arr, mid + 1, end);
9              return n;
10     }
11        
12     public static TreeNode createMinimalBST(int array[]) {
13             return addToTree(array, 0, array.length - 1);
14     }

Given a directed graph, design an algorithm to find out whether there is a route be- tween two nodes.

This problem can be solved by just simple graph traversal, such as depth first search or breadth first search. We start with one of the two nodes and, during traversal, check if the other node is found. We should mark any node found in the course of the algorithm as ‘already visited’ to avoid cycles and repetition of the nodes.

1       public enum State {
2               Unvisited, Visited, Visiting;
3       }
4   
5       public static boolean search(Graph g, Node start, Node end) {
6               LinkedList<Node> q = new LinkedList<Node>(); // operates as Stack
7               for (Node u : g.getNodes()) {
8                        u.state = State.Unvisited;
9               }
10              start.state = State.Visiting;
11              q.add(start);
12              Node u;
13              while(!q.isEmpty()) {
14                       u = q.removeFirst(); // i.e., pop()
15                       if (u != null) {
16                               for (Node v : u.getAdjacent()) {
17                                       if (v.state == State.Unvisited) {
18                                               if (v == end) {
19                                                       return true;
20                                               } else {
21                                                       v.state = State.Visiting;
22                                                       q.add(v);
23                                               }
24                                       }
25                               }
26                               u.state = State.Visited;
27                       }
28              }
29              return false;
30      }

Check if Tree is balanced

                          The difference of min depth and max depth should not exceed 1,
since the difference of the min and the max depth is the maximum distance difference possible in the tree.

1       public static int maxDepth(TreeNode root) {
2                if (root == null) {
3                        return 0;
4                }
5                return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
6       }
7                  
8       public static int minDepth(TreeNode root) {
9                if (root == null) {
10                       return 0;
11               }
12               return 1 + Math.min(minDepth(root.left), minDepth(root.right));
13      }
14             
15      public static boolean isBalanced(TreeNode root){
16               return (maxDepth(root) - minDepth(root) <= 1);
17      }

Is given tree foldable

/* Returns true if the given tree is foldable */

bool isFoldable(struct node *root)

{

  bool res;

 

  /* base case */

  if(root == NULL)

    return true;

 

  /* convert left subtree to its mirror */

  mirror(root->left);

 

  /* Compare the structures of the right subtree and mirrored

    left subtree */

  res = isStructSame(root->left, root->right);

 

  /* Get the originial tree back */

  mirror(root->left);

 

  return res;

}

 

bool isStructSame(struct node *a, struct node *b)

{

  if (a == NULL && b == NULL)

  {  return true; }

  if ( a != NULL && b != NULL &&

       isStructSame(a->left, b->left) &&

       isStructSame(a->right, b->right)

     )

  {  return true; }

 

  return false;

}   

 

Check if given two trees are identical to each other

   public static boolean isIdentical(BinaryTree root, BinaryTree root1){
     if(root1==null && root==null)
        return true;
     else if(root1!=null && root!=null){
      if(root1.value==root.value)
        return(isIdentical(root1.left,root.left) && isIdentical(root1.right,root.right));
      }
     return false;
     
   }

Check Whether given Tree is a BST or not

  public static boolean isBST(BinaryTree root){
    int min=-9999;
    int max=9999;
    return(isBSTUtil(root,min,max));
   
  }
 
 
  public static boolean isBSTUtil(BinaryTree node, int min, int max){
    if(node==null)
      return true;
    if(node.value < min || node.value > max)
      return false;
    return(isBSTUtil(node.left, min, node.value) && (isBSTUtil(node.right,node.value +1, max)));
  }

Depth of a given node in BT

public static int depth(BinaryTree root,int node_value){
       Queue<BinaryTree> q = new LinkedList<BinaryTree>();
       int depth=1;
     
       q.add(root);
       q.add(null);
       while(!q.isEmpty()){
      boolean isAdded =false;
      BinaryTree temp = q.poll();
      if(temp==null)
             depth=depth+1;
      else{
      if(temp.data==node_value)
      return depth;
      if(temp.left!=null){
      isAdded=true;
      q.add(temp.left);
      }
      if(temp.right!=null){
      isAdded=true;
      q.add(temp.right);
      }
      if(isAdded)
         q.add(null);
      }
       }
     return 0;
}

Minsum and maxsum in a given Binary Tree

public static int maxSum(BinaryTree root,int maxsum){
maxsum = maxsum + root.value;
if(root==null)
return 0;
if(root.left==null && root.right==null){
return maxsum;
}
return(Math.max(maxSum(root.left,maxsum),maxSum(root.right,maxsum)));
}

public static int minSum(BinaryTree root,int minsum){
minsum = minsum + root.value;
if(root==null)
return 0;
if(root.left==null && root.right==null){
return minsum;
}
return(Math.min(minSum(root.left,minsum),minSum(root.right,minsum)));
}

Finding the path in a binary tree with given sum

public static boolean  hasPathSum(BinaryTree root, int sum){
if(root==null)
return(sum==0);
else
{
sum=sum-root.value;
return(hasPathSum(root.left,sum) || hasPathSum(root.right,sum));

}

}

Diameter of a tree

The function below returns the diameter of a tree. A tree's diameter is defined after the function. Write a recurrence for this function and solve it yielding the running time using big-Oh in terms of the number of nodes in a tree.


int diameter(Tree * t)
// post: return diameter of t
{
    if (t == 0) return 0;

    int lheight = height(tree-&gt;left);
    int rheight = height(tree-&gt;right);

    int ldiameter = diameter(tree-&gt;left);
    int rdiameter = diameter(tree-&gt;right);

    return max(lheight + rheight + 1,
      max(ldiameter,rdiameter));
}

The following function returns the height of a tree (the number of nodes on the longest root-to-leaf path).

    int height(Tree * t)
    // postcondition: returns height of tree with root t
    {
        if (t == 0)
        {
            return 0;
        }
        else
        {
            return 1 + max(height(t-&gt;left),height(t-&gt;right));
        }
    }

Printing paths from root to all leaf nodes

/**
 Given a binary tree, prints out all of its root-to-leaf
 paths, one per line. Uses a recursive helper to do the work.
*/
public void printPaths() {
  int[] path = new int[1000];
  printPaths(root, path, 0);
}
/**
 Recursive printPaths helper -- given a node, and an array containing
 the path from the root node up to but not including this node,
 prints out all the root-leaf paths.
*/
private void printPaths(Node node, int[] path, int pathLen) {
  if (node==null) return;

  // append this node to the path array
  path[pathLen] = node.data;
  pathLen++;

  // it's a leaf, so print the path that led to here
  if (node.left==null && node.right==null) {
    printArray(path, pathLen);
  }
  else {
  // otherwise try both subtrees
    printPaths(node.left, path, pathLen);
    printPaths(node.right, path, pathLen);
  }
}

/**
 Utility that prints ints from an array on one line.
*/
private void printArray(int[] ints, int len) {
  int i;
  for (i=0; i<len; i++) {
   System.out.print(ints[i] + " ");
  }
  System.out.println();
}

Height of a tree Iterative n recursive pgm

public static void height(BinaryTree root){
int height=-1;
Queue<BinaryTree> q=new LinkedList<BinaryTree>();
BinaryTree curr;
q.add(root);
q.add(null);
while(!q.isEmpty()){
curr=q.poll();
if(curr==null){
height++;
if(!q.isEmpty())
    q.add(null);
}
else{
if(curr.left!=null)
q.add(curr.left);
if(curr.right!=null)
q.add(curr.right);
}
}
System.out.println(height);
}



public static int height_rec(BinaryTree root){
            if(root==null)
return -1;
   else
return(max(height_rec(root.left),height_rec(root.right)) + 1);
}

Mirroring a Tree Iterative n Recursive

public static void iterative_mirror(BinaryTree root){
if(root==null) return;
   Queue<BinaryTree> q= new LinkedList<BinaryTree>();
   q.add(root);
   BinaryTree curr,temp;
   while(!q.isEmpty()){
curr=q.poll();
temp=curr.left;
curr.left=curr.right;
curr.right=temp;
if(curr.left!=null)
q.add(curr.left);
if(curr.right!=null)
q.add(curr.right);
   }
   LevelOrder(root);
}

public static void rec_mirror(BinaryTree root){
BinaryTree temp;
   if(root==null) return;
   else {
 
  rec_mirror(root.left);
  rec_mirror(root.right);
  temp = root.left;
  root.left=root.right;
  root.right=temp;
   }
   
}

Iterative Traversals in Java

package Tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author ssundara
 *
 */
public class BinaryTree1 {
 
  BinaryTree1 left;
  BinaryTree1 right;
  int value;

  BinaryTree1(int value){
    this.value=value;
   
}
 
  /**
   * @param args
   */
  public static void main(String[] args){
   
    BinaryTree root=new BinaryTree(20);
    insert(root,8);
    insert(root,4);
   
    insert(root,22);
   
    insert(root,12);
    insert(root,10);
    insert(root,14);
    iterative_inorder(root);
    iterative_Preorder(root);
    iterative_Postorder(root);

}
 
  public static void insert(BinaryTree node, int value){
   if(value<node.value){
     if(node.left!=null)
       insert(node.left,value);
     else
       node.left=new BinaryTree(value);
   }
   if(value>node.value){
     if(node.right!=null)
       insert(node.right,value);
     else
       node.right=new BinaryTree(value);
   }
}
 
  public static void iterative_inorder(BinaryTree root){
 BinaryTree curr;
 Stack<BinaryTree> stk = new Stack<BinaryTree>();
 boolean done = false;
 stk.push(root);
 while(!stk.isEmpty()){
 done=false;
BinaryTree temp = stk.peek();
if(temp.left!=null)
stk.push(temp.left);

else {
while(!done){
if(stk.isEmpty()) return;
curr = stk.pop();
   System.out.println(curr.value);
curr=curr.right;
if(curr!=null){
done=true;
stk.push(curr);
}
}
 }
  }
  }
 
  public static void iterative_Preorder(BinaryTree root){
 BinaryTree curr;
 Stack<BinaryTree> stk = new Stack<BinaryTree>();
 boolean done = false;
 stk.push(root);
 System.out.println("DFS");
 System.out.print(root.value + " ");
 while(!stk.isEmpty()){
 done=false;
BinaryTree temp = stk.peek();
if(temp.left!=null){
stk.push(temp.left);
System.out.print(temp.left.value + " ");
}

else {
while(!done){
if(stk.isEmpty()) return;
curr = stk.pop();
   curr=curr.right;
if(curr!=null){
done=true;
stk.push(curr);
System.out.print(curr.value + " ");

}
}
 }
  }
  }
 
 
public static void iterative_Postorder(BinaryTree root){
 BinaryTree curr,tmp=null;
 System.out.println("asdfasdf");
 Stack<BinaryTree> stk = new Stack<BinaryTree>();
boolean pop=false;
 stk.push(root);
 while(!stk.isEmpty()){
BinaryTree temp = stk.peek();
if(temp.left!=null && !pop)
stk.push(temp.left);
else {
curr = stk.peek();
curr=curr.right;
if(curr!=null && curr!=tmp){
stk.push(curr);
pop=false;
}
else{
tmp = stk.pop();
pop=true;
System.out.println(tmp.value);
}
}
}
}
}

Traversals in a binary Tree

package Tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;




/**
 * @author ssundara
 *
 */
public class BinaryTree {
 
  BinaryTree left;
  BinaryTree right;
  int value;

  BinaryTree(int value){
    this.value=value;
   
  }
 
  /**
   * @param args
   */
  public static void main(String[] args){
   
    BinaryTree root=new BinaryTree(20);
    insert(root,8);
    insert(root,12);
    insert(root,4);
    insert(root,22);
    insert(root,14);
    insert(root,10);
    //insert(root,50);
    System.out.print("Inorder   :");
    Inorder(root);
    System.out.println();
    System.out.print("Preorder  :");
    Preorder(root);
    System.out.println();
    System.out.print("Postorder   :");
    Postorder(root);
    System.out.println();
    System.out.print("Level order  :");
    LevelOrder(root);
    System.out.println();
    System.out.print("Spiral order  :");
    SpiralOrder(root);
    System.out.println();
    System.out.print("DFS  :");
    dfs(root);
  }
 
  public static void insert(BinaryTree node, int value){
    if(value<node.value){
      if(node.left!=null)
        insert(node.left,value);
      else
        node.left=new BinaryTree(value);
    }
   
    if(value>node.value){
      if(node.right!=null)
        insert(node.right,value);
      else
        node.right=new BinaryTree(value);
    }
  
  }
 
  public static void Inorder(BinaryTree root){
    if(root!=null){
    Inorder(root.left);
    System.out.print(root.value + " ");
    Inorder(root.right);
     
   }
}
 
  public static void Preorder(BinaryTree root){
    if(root!=null){
      System.out.print(root.value + " "); 
    Inorder(root.left);
    Inorder(root.right);
     
    }
}
 
  public static void Postorder(BinaryTree root){
    if(root!=null){
    Inorder(root.left);
    Inorder(root.right);
    System.out.print(root.value + " ");
    }
}
 
  public static void LevelOrder(BinaryTree root){
    Queue<BinaryTree> q=new LinkedList<BinaryTree>();
    q.add(root);
    while(!q.isEmpty()){
      System.out.print(q.poll().value + " ");
      if(root.left!=null)
        q.add(root.left);
      if(root.right!=null)
        q.add(root.right);
      if(q.peek()!=null)
        root=q.peek();

    }
   
    }
 
  public static void SpiralOrder(BinaryTree root){
    Stack<BinaryTree> st1=new Stack<BinaryTree>();
    Stack<BinaryTree> st2=new Stack<BinaryTree>();
    BinaryTree temp=null;
    st1.push(root);
 
    while(!st1.isEmpty() || !st2.isEmpty()){
    while(!st1.isEmpty()){
      if(st1.peek()!=null)
        temp=st1.peek();
      System.out.print(st1.pop().value + " ");
      if(temp.left!=null)
        st2.push(temp.left);
      if(temp.right!=null)
        st2.push(temp.right);
    }
    while(!st2.isEmpty()){
      if(st2.peek()!=null)
        temp=st2.peek();
      System.out.print(st2.pop().value + " ");
      if(temp.right!=null)
        st1.push(temp.right);
      if(temp.left!=null)
        st1.push(temp.left);
     
    }
  }
  }
 
  public static void dfs(BinaryTree root) {
    Stack<BinaryTree> st1=new Stack<BinaryTree>();
    BinaryTree temp;
    BinaryTree tmp;
    st1.push(root);
    System.out.print(root.value + " ");
   
    while(!st1.isEmpty()){
     temp=st1.peek();
     if(temp.left!=null){
       st1.push(temp.left);
       System.out.print(temp.left.value + " ");
      
      
      
     }
     else{
       tmp=st1.peek();
       while(tmp.right==null){
         if(st1.isEmpty()) return;
         tmp=st1.pop();
       }
       st1.push(tmp.right);
       System.out.print(tmp.right.value + " ");
      
     }
    }
  }
}





Output :

Inorder   :4 8 10 12 14 20 22
Preorder  :20 4 8 10 12 14 22
Postorder   :4 8 10 12 14 22 20
Level order  :20 8 22 4 12 10 14
Spiral order  :20 22 8 4 12 14 10
DFS  :20 8 4 12 10 14 22

LCA of two given nodes in BST

public class LCA {
 
 
    LCA left;
    LCA right;
    int data;
 
    LCA(int data){
      this.data=data;
    }
 
  public static void main(String[] args) {
    LCA root=new LCA(20);
    insert(root,8);
    insert(root,12);
    insert(root,4);
    insert(root,22);
    insert(root,14);
    insert(root,10);
    preorder(root);
    find_lca(root,14,4);
   
  }
 
  public static void insert(LCA node,int data){
    if(node.data > data){
      if(node.left!=null)
        insert(node.left,data);
      else
        node.left=new LCA(data);
    }
    if(node.data < data){
      if(node.right!=null)
        insert(node.right,data);
      else
        node.right=new LCA(data);
     
    }
  }
 
 
  public static void find_lca(LCA root, int data1, int data2){
    if(root.data == data1 || root.data == data2){
      System.out.println("One of the given input is root node. No LCA");
      return;
    }
    while(root!=null ){
      if(root.left ==null || root.right==null) {
         System.out.println("One or both of the datas given is not existing in the tree");
         break;
      }
     
     else if(root.data < data1 && root.data < data2){
       if(root.right.data == data1 || root.right.data == data2){
         System.out.println("LCA : " + root.data);
         break;
       }
       root=root.right;
     }
     
    
     else if(root.data > data1 && root.data > data2){
       if(root.left.data == data1 || root.left.data == data2){
         System.out.println("LCA : " + root.data);
         break;
       }
       root=root.left;
     }
     
    
    else{
      System.out.println("LCA of" + data1 + "and" + data2 + "is" + root.data);
       break;
      }
  }
   
  }
 
  public static void preorder(LCA root){
   if(root!=null) {
   System.out.println(root.data);
   preorder(root.left);
   preorder(root.right);
  }
  }
}

Recursive :
http://www.cracktheinterview.in/viewtopic.php?f=2&t=92&sid=9fb3ab9e038d3641cb5f39e3b6f3c777