|
package
com.kartik.recursive;
import java.util.Map.Entry;
import java.util.Queue;
import java.util.Stack;
import java.util.LinkedList;
import java.util.TreeMap;
public class BinaryTree {
public static class TreeNode {
int data;
TreeNode left;
TreeNode right;
TreeNode(int data) {
this.data=data;
}
}
/**
* <ul><b><i> Steps for InOrder traversal
are:</i></b></ul>
* <li>Traverse the left subtree in InOrder.</li>
* <li>Visit the node.</li>
* <li>Traverse the right subtree in InOrder.</li>
*
* @param root
*/
public void inOrder(TreeNode root) {
if(root != null) {
inOrder(root.left);
//Visit the node by Printing the node data
System.out.printf("%d ",root.data);
inOrder(root.right);
}
}
/**
* <ul><b><i> Steps for Pre order traversal
are:</i></b></ul>
* <li>Visit the node.</li>
* <li>Traverse the left subtree in preOrder.</li>
* <li>Traverse the right subtree in preOrder.</li>
*
* @param root
*/
public void preorder(TreeNode root) {
if(root != null) {
//Visit the node by Printing the node data
System.out.printf("%d ",root.data);
preorder(root.left);
preorder(root.right);
}
}
/**
* <ul><b><i> Steps for post Order traversal
are:</i></b></ul>
* <li>Traverse the left subtree in post Order.</li>
* <li>Traverse the right subtree in post Order.</li>
* <li>Visit the node.</li>
*
* @param root
*/
public void postorder(TreeNode root) {
if(root != null) {
postorder(root.left);
postorder(root.right);
//Visit the node by Printing the node data
System.out.printf("%d ",root.data);
}
}
/**
* <ul><b><i> Steps for print leaf
node:</i></b></ul>
* <li>Visit the node. if node left and node right both are
null</li>
* <li>Traverse the left subtree in post Order.</li>
* <li>Traverse the right subtree in post Order.</li>
*
* @param root
*/
public void printLeafNodes(TreeNode node) {
if(node==null) return;
if(node.left == null && node.right == null) {
System.out.printf("%d ",node.data);
}
printLeafNodes(node.left);
printLeafNodes(node.right);
}
/**
* <ul><b><i> prints spiral/zigzag level order Steps
for solution:</i></b></ul>
* <li>Create an empty stack s and push root to it.</li>
* <li>while stack is not NULL Do following</li>
* <li>Create a empty stack called tempStack.</li>
* <li>Pop a node from stack and push it to tempStack
depending on directionFlag</li>
* <li>Change directionFlag to change the direction of
traversal</li>
* <li>set stack=tempStack</li>
*
* @param root
*/
public void spiralOrZigzagLevelOrder(TreeNode root) {
if(root==null) return;
Stack<TreeNode> stack=new Stack<TreeNode>();
stack.push(root);
boolean directionflag=false;
while(!stack.isEmpty()) {
Stack<TreeNode> tempStack=new Stack<TreeNode>();
while(!stack.isEmpty()) {
TreeNode tempNode=stack.pop();
System.out.printf("%d ",tempNode.data);
if(!directionflag) {
if(tempNode.left!=null)
tempStack.push(tempNode.left);
if(tempNode.right!=null)
tempStack.push(tempNode.right);
}else {
if(tempNode.right!=null)
tempStack.push(tempNode.right);
if(tempNode.left!=null)
tempStack.push(tempNode.left);
}
}
// for changing direction
directionflag=!directionflag;
stack=tempStack;
}
}
/**
* <ul>
* <b><i> We will use Queue for Level Order traversal.This
algorithm is very
* similar to Breadth first search of graph. Steps for Level order
traversal
* algorithm:</i></b>
* </ul>
* <li>Create empty queue and push root node to it.</li>
<li>Do the following
* when queue is not empty</li> <li>Pop a node from queue
and print it</li>
* <li>Push left child of popped node to queue if not
null</li> <li>Push
* right child of popped node to queue if not null</li>
*
* @param root
*/
public void levelOrderTraversal(TreeNode startNode) {
Queue<TreeNode> queue=new LinkedList<TreeNode>();
queue.add(startNode);
while(!queue.isEmpty()) {
TreeNode tempNode=queue.poll();
System.out.print(tempNode.data+" ");
if(tempNode.right!=null)
queue.add(tempNode.right);
if(tempNode.left!=null)
queue.add(tempNode.left);
}
}
/**
* <ul>
* <b><i> Steps for Reverse Level order traversal
algorithm:</i></b>
* </ul>
* <li>Create empty queue and push root node to it.</li>
<li>Do the following
* when queue is not empty</li> <li>Pop a node from queue
and print it</li>
* <li>Push right child of popped node to queue if not
null</li> <li>Push
* left child of popped node to queue if not null</li>
* <li>Push current node to stack</li>
* <li>Pop node from stack and print it</li>
*
* @param root
*/
public void reverseLevelOrderTraversal(TreeNode startNode) {
Queue<TreeNode> queue=new LinkedList<TreeNode>();
Stack<TreeNode> stack=new Stack<TreeNode>();
queue.add(startNode);
while(!queue.isEmpty()) {
TreeNode tempNode=queue.poll();
if(tempNode.right!=null)
queue.add(tempNode.right);
if(tempNode.left!=null)
queue.add(tempNode.left);
stack.push(tempNode);
}
while(!stack.empty())
System.out.print(stack.pop().data+" " );
}
public void printSumOfVerticalLevel(TreeNode startNode) {
System.out.println("Vertical sum of binary tree will be:");
TreeMap<Integer, Integer> treeNodeMap = new TreeMap<Integer,
Integer>();
printVertivalSumOfBinaryTree(startNode, treeNodeMap, 0);
for (Entry<Integer, Integer> entry : treeNodeMap.entrySet()) {
System.out.print(entry.getValue() + " ");
}
}
// prints vertical sum in binary tree
public void printVertivalSumOfBinaryTree(TreeNode startNode,
TreeMap<Integer, Integer> treeNodeMap, int level) {
if (startNode == null) {
return;
}
// Decrease level by 1 when iterating left child
printVertivalSumOfBinaryTree(startNode.left, treeNodeMap, level - 1);
if (treeNodeMap.get(level) != null) {
// Adding current node data to previous stored value to get the
sum
Integer sum = treeNodeMap.get(level) + startNode.data;
treeNodeMap.put(level, sum);
} else {
treeNodeMap.put(level, startNode.data);
} // Increase level by 1 when iterating left child
printVertivalSumOfBinaryTree(startNode.right, treeNodeMap, level + 1);
}
public void printAllPathFromRootToLeaf(TreeNode node) {
printAllPathsToLeaf(node, new int[1000], 0);
}
// Prints all paths to leaf
public void printAllPathsToLeaf(TreeNode node, int[] path, int len) {
if (node == null)
return;
// storing data in array
path[len] = node.data;
len++;
if (node.left == null && node.right == null) {
// leaf node is reached
printArray(path, len);
return;
}
printAllPathsToLeaf(node.left, path, len);
printAllPathsToLeaf(node.right, path, len);
}
public void printArray(int[] path, int len) {
for (int i = 0; i < len; i++) {
System.out.print(" " + path[i]);
}
System.out.println();
}
// TR-20010 Start
public boolean checkSubtree(TreeNode
rootA, TreeNode rootB) {
String inOrderA = inOrder(rootA);
String inOrderB = inOrder(rootB);
String postOrderA = postorder(rootA);
String postOrderB = postorder(rootB);
return
(inOrderA.toLowerCase().contains(inOrderB.toLowerCase()) &&
postOrderA
.toLowerCase().contains(postOrderB.toLowerCase()));
}
// TR-20010 End
// TR-20011 Start
public static int pIndex = 0;
public TreeNode makeBTree(int[]
inOrder, int[] postOrder, int inOrderStart,
int inOrderEnd, int postOrderStart,
int postOrderEnd) {
if (inOrderStart > inOrderEnd ||
postOrderStart > postOrderEnd) {
return null;
}
int rootValue =
postOrder[postOrderEnd];
TreeNode root = new
TreeNode(rootValue);
pIndex++;
if (inOrderStart == inOrderEnd) {
return root;
}
int index = getInorderIndex(inOrder,
inOrderStart, inOrderEnd,
root.data);
root.left = makeBTree(inOrder,
postOrder, inOrderStart, index - 1,
postOrderStart, postOrderStart +
index - (inOrderStart + 1));
root.right = makeBTree(inOrder,
postOrder, index + 1, inOrderEnd,
postOrderStart + index -
inOrderStart, postOrderEnd - 1);
return root;
}
public int getInorderIndex(int[]
inOrder, int start, int end, int data) {
for (int i = start; i <= end; i++)
{
if (inOrder[i] == data) {
return i;
}
}
return -1;
}
// TR-20011 End
// TR-200012 Start
public static int sum = 0;
public void greaterTree(TreeNode root)
{
if (root != null) {
// visit the right node first
greaterTree(root.right);
// store the node value in temp
int temp = root.data;
// update the sum, sum till previous
visited node
root.data = sum;
// update the sum for the next node
sum = sum + temp;
greaterTree(root.left);
} else
return;
}
// Tr-200012 End
public static void main(String[] args) {
BinaryTree bi=new BinaryTree();
//Creating a binary tree
TreeNode rootNode=createBinaryTree();
System.out.println("Display Tree in In-order");
bi.inOrder(rootNode);
System.out.println();
System.out.println("Display Tree in pre-order");
bi.preorder(rootNode);
System.out.println();
System.out.println("Display Tree in post-order");
bi.postorder(rootNode);
System.out.println();
System.out.println("Display leaf node of binary tree");
bi.printLeafNodes(rootNode);
System.out.println();
System.out.println("Spiral/Zigzag traversal of binary tree
:");
//two stack one for temp another one simple and one flag
bi.spiralOrZigzagLevelOrder(rootNode);
System.out.println();
System.out.println("level Order traversal ");//only one
queue
bi.levelOrderTraversal(rootNode);
System.out.println();
System.out.println("Reverse order traversal ");
bi.reverseLevelOrderTraversal(rootNode);
//only one queue and one stack and first right next left node visit
System.out.println();
bi.printSumOfVerticalLevel(rootNode);
System.out.println();
System.out.println("Root to Leaf node root ");
bi.printAllPathFromRootToLeaf(rootNode);
System.out.println();
System.out.println("Sub Tree testing---->");
TreeNode subRoot=createBinarySubTree();
System.out.println(bi.checkSubtree(rootNode,subRoot));
System.out.println();
System.out.println("How to make inorder and post order data to a
Binary tree");
int[] inOrder = { 4, 2, 5, 1, 6, 3, 7 };
int[] postOrder = { 4, 5, 2, 6, 7, 3, 1 };
TreeNode x= bi.makeBTree(inOrder, postOrder, 0, inOrder.length-1, 0,
postOrder.length-1);
System.out.println("Inorder Print --->"+bi.inOrder(x));
System.out.println("Postorder Print --->"+bi.postorder(x));
System.out.println();
System.out.println("Greater sum of a tree-->");
bi.greaterTree(rootNode);
System.out.println(bi.inOrder(rootNode));
}
public static TreeNode createBinaryTree() {
TreeNode rootNode =new TreeNode(40);
TreeNode node20=new TreeNode(20);
TreeNode node10=new TreeNode(10);
TreeNode node30=new TreeNode(30);
TreeNode node60=new TreeNode(60);
TreeNode node50=new TreeNode(50);
TreeNode node70=new TreeNode(70);
TreeNode node5=new TreeNode(5);
TreeNode node55=new TreeNode(55);
rootNode.left=node20;
rootNode.right=node60;
node20.left=node10;
node20.right=node30;
node60.left=node50;
node60.right=node70;
node10.left=node5;
node50.right=node55;
return rootNode;
}
public static TreeNode createBinarySubTree() {
TreeNode rootNode=new
TreeNode(20);
TreeNode node10=new
TreeNode(10);
TreeNode node30=new
TreeNode(30);
TreeNode node5=new
TreeNode(5);
rootNode.left=node10;
rootNode.right=node30;
node10.left=node5;
return rootNode;
}
}
|
0 Comments