Tree Algorithms

How to determine if a Binary Tree is balanced or not?
 

package com.saroj.tree;
/**
 * @author saroj
 *
 */
public class BalancedTreeDemo {
    public boolean isBalanced(Tree node){
	if(node == null) return false;
	  if(getHeight(node) == -1){
	    return false;
	  }
          else
          {
	   return true;
	   }
	}
	
    public int getHeight(Tree node){
	int leftH = getHeight(node.leftT);
	int rightH = getHeight(node.rightT);
	    if(leftH == -1 || rightH == -1){
	        return -1;
	    }
	int diff = leftH-rightH;
	    if(diff > 1){
	      return -1;
	    }else{
	      return Math.max(leftH, rightH)+1;
	    }
	}
	
 static class Tree{
	Tree leftT;
	Tree rightT;
	int data;
}
}

How to find the depth of a Binary Tree?

package com.saroj.tree;
import java.util.LinkedList;
import java.util.Queue;

public class DepthOfATree {
  public int getDepth(TreeNode root){
     if(root == null) return 0;
	Queue nodes = new LinkedList();
	Queue counts = new LinkedList();
	nodes.add(root);
	counts.add(1);
	while(!nodes.isEmpty()){
	     TreeNode curr = nodes.remove();
	     int count = counts.remove();
	     if(curr.left !=null){
		nodes.add(curr.left);
		counts.add(count+1);
	     }
	     if(curr.right !=null){
		nodes.add(curr.right);
		counts.add(count+1);
	     }	
	     if(curr.left == null && curr.right ==null){
		return count;
	     }
		}
		return 0;
	}
   class TreeNode{
	int data;
	TreeNode left;
	TreeNode right;
	public TreeNode(int val){
	   this.data=val;
	}
  }

}

Writing a InOrder traversal Binary tree in a recursive way
The order is left node -> parent -> right node

public class InOrderBST {
    static final List list = new ArrayList();
	private static List inOrder(Tree node){
	     if(node !=null) 
             {
	        traverse(node);
	     }
	      return list;
	}
	
	private static void traverse(Tree root){
	      if(root.leftT !=null){
		    traverse(root.leftT);
		}
		list.add(root.val);
		if(root.rightT !=null){
		    traverse(root.rightT);
		}
	}

	static class Tree{
		Tree leftT;
		Tree rightT;
		int val;
		Tree(int data){
		   this.val=data;
		}
	}
}

Writing the InOrder Binary Tree in Iterative way

private static List inOrder(Tree root){
	List myList = new ArrayList();
	  if(root == null) return myList;
	  Stack myStack = new Stack();
	  Tree current = root;
	  while(!myStack.isEmpty()){
	    if(current != null){
		myStack.push(current);
		current = current.leftT;
	     }else {
		Tree node = myStack.pop();
		myList.add(node.data);
		current = node.rightT;
	      }
	    }
	    return myList;	
	}

Writing PreOrder Binary Tree
The order is: parent -> left node – > right node

public class PreOrderBST {
     private static List preOrder(TreeNode root){	
	List list = new ArrayList();
	Stack myStack = new Stack();
	if(root == null) return list;
	myStack.push(root);
	while(!myStack.isEmpty()){
	   TreeNode node = myStack.pop();
	   list.add(node.data);
		if(node.rightT !=null){
		   myStack.push(node.rightT);
		}
		if(node.leftT !=null){
		    myStack.push(node.leftT);
		}
	   }
	   return list;	
	}
	
static class TreeNode {
    TreeNode leftT;
    TreeNode rightT;
    int data;
 }

}

Find the lowest common ancestor of 2 nodes in a Binary Tree

public class LcaBST {
	
     public static void main(String[] args) {
	
	TreeNode node = new TreeNode(15);
	node.leftT = new TreeNode(12);
	node.rightT = new TreeNode(20);
	node.leftT.leftT = new TreeNode(10);
	node.leftT.rightT = new TreeNode(14);
		
	node.rightT = new TreeNode(20);
	node.rightT.leftT = new TreeNode(19);
	node.rightT.rightT=new TreeNode(22);
		
	int n1=19, n2=22;
	TreeNode t = lca(node, n1, n2);
	System.out.println("lca of "+n1+"and "+n2+"is "+t.data);
		
	}
     private static TreeNode lca(TreeNode node, int n1, int n2){
	if(node == null) return null;
	if(node.data > n1 && node.data > n2){
		return lca(node.leftT,n1, n2);
	}
	if(node.data < n1 && node.data < n2){
		return lca(node.rightT, n1, n2);
	}
		return node;
	}
static class TreeNode {
	TreeNode leftT, rightT;
	int data;
		
	TreeNode(int val){
	    this.data=val;
	    leftT=rightT=null;
	}
  }

}

Mirroring a binary Tree

public class MirrorBinaryTree {

  public TreeNode mirrorBinary(TreeNode node){
    if(node == null || node.getLeftChild()==null || node.getRightChild() ==null){
      return null;
    }
    else{
      TreeNode current = node;
      Stack myStack = new Stack();
      myStack.push(node);
      while(!myStack.isEmpty()){
        myStack.pop();
        TreeNode temp = current.getLeftChild();
        current.leftChild=current.rightChild;
        current.rightChild=temp;
        if(current.leftChild !=null){
          myStack.push(current.leftChild);
        }
        if(current.rightChild !=null){
          myStack.push(current.rightChild);
        }
      }
      return node;
    }
  }
}

Check if a binary tree is subtree of another binary tree

public class SubTreeTest {

	private static boolean areIdentical(TreeNode t1, TreeNode t2){
		if(t1 == null && t2 == null){
			return true;
		}
		if(t1 == null || t2 == null){
			return false;
		}
		return (t1.data == t2.data && areIdentical(t1.leftT, t2.leftT) && areIdentical(t1.rightT, t2.rightT));
	}
	// lets say node1 is subtree of node2
	private static boolean isSubTree(TreeNode node1, TreeNode node2){
		if(node1 == null) return true;
		if(node2 == null) return false;
		if(areIdentical(node1, node2)) return true;
		return isSubTree(node1, node2.leftT) || isSubTree(node1,node2.rightT);
	}
	
	static class TreeNode{
		TreeNode leftT;
		TreeNode rightT;
		int data;
		
		TreeNode(int val){
			this.data=val;
			leftT = rightT = null;
		}
	}
	
    public static void main(String[] args) {
		
    	TreeNode node1 = new TreeNode(10);
    	node1.leftT = new TreeNode(9);
    	node1.rightT = new TreeNode(12);
    	
    	TreeNode node2 = new TreeNode(20);
    	node2.leftT = new TreeNode(10);
    	node2.leftT.leftT = new TreeNode(9);
    	node2.leftT.rightT = new TreeNode(12);
    	
    	node2.rightT = new TreeNode(22);
    	node2.rightT.leftT = new TreeNode(21);
    	node2.rightT.rightT= new TreeNode(24);
    	
    	boolean result = isSubTree(node1, node2);
    	System.out.println("Are these 2 nodes satisfy the subtree: "+result);
	}

}