import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Stack;
public class AllTreeTraversal {
static Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
public static void preOrderTraversal(TreeBNode root) {
if (null != root) {
System.out.print(root.data + " ");
preOrderTraversal(root.leftChild);
preOrderTraversal(root.rightChild);
}
}
public static void preOrderWithoutRec(TreeBNode root) {
Stack s = new Stack<>();
if (null == root) {
return;
}
else {
s.push(root);
while (!s.isEmpty()) {
TreeBNode temp = s.pop();
System.out.print(temp.data + " ");
if (temp.rightChild != null) {
s.push(temp.rightChild);
}
if (temp.leftChild != null) {
s.push(temp.leftChild);
}
}
}
}
public static void inOrderTraversal(TreeBNode root) {
if (null != root) {
inOrderTraversal(root.leftChild);
System.out.print(root.data + " ");
inOrderTraversal(root.rightChild);
}
}
public static void INOrderWithoutREC(TreeBNode root){
if ( null == root){
return;
}else{
Stack st = new Stack();
boolean completed = false;
TreeBNode current = root;
while(!completed){
if(null!=current){
st.push(current);
current = current.leftChild;
}else{
if(st.isEmpty()){
completed = true;
}else{
current = st.pop();
System.out.print(current.data+" ");
current = current.rightChild;
}
}
}
}
}
public static void inOrderIter(TreeBNode root) {
if(root == null)
return;
Stack s = new Stack();
TreeBNode currentNode=root;
while(!s.empty() || currentNode!=null){
if(currentNode!=null)
{
s.push(currentNode);
currentNode=currentNode.leftChild;
}
else
{
TreeBNode n=s.pop();
System.out.printf("%d ",n.data);
currentNode=n.rightChild;
}
}
}
public static void postOrderTraversal(TreeBNode root) {
if (null != root) {
postOrderTraversal(root.leftChild);
postOrderTraversal(root.rightChild);
System.out.print(root.data + " ");
}
}
public static void postOrderWithoutRecu(TreeBNode root) {
Stack s = new Stack<>();
Stack s1 = new Stack<>();
s.push(root);
while(!s.isEmpty()) {
TreeBNode temp = s.pop();
s1.push(temp);
if(temp.leftChild!=null) {
s.push(temp.leftChild);
}
if(temp.rightChild!=null) {
s.push(temp.rightChild);
}
}
while(!s1.isEmpty()) {
System.out.print(s1.pop().data+" ");
}
}
public static void levelOrderTraversal(TreeBNode root) {
int max = Integer.MIN_VALUE;
if (null == root) {
return;
}
else {
Queue queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeBNode temp = queue.poll();
System.out.println(temp.data);
if (temp.data > max) {
max = temp.data;
}
if (null != temp.leftChild) {
queue.offer(temp.leftChild);
}
if (null != temp.rightChild) {
queue.offer(temp.rightChild);
}
}
}
System.out.println("maximum element is " + max);
}
void printLevelOrder(TreeBNode root) {
Queue queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeBNode tempTreeBNode = queue.poll();
System.out.print(tempTreeBNode.data + " ");
if (tempTreeBNode.leftChild != null) {
queue.add(tempTreeBNode.leftChild);
}
if (tempTreeBNode.rightChild != null) {
queue.add(tempTreeBNode.rightChild);
}
}
} public void printSpiral(TreeBNode root2, TreeBNode root) {
Stack s1 = new Stack();
Stack s2 = new Stack();
s1.push(root);
while (!s1.isEmpty() || !s2.isEmpty()) {
while (!s1.isEmpty()) {
TreeBNode temp = s1.peek();
s1.pop();
System.out.print(temp.data + " ");
if (temp.rightChild != null) {
s2.push(temp.rightChild);
}
if (temp.leftChild != null) {
s2.push(temp.leftChild);
}
}
while (!s2.isEmpty()) {
TreeBNode temp = s2.peek();
s2.pop();
System.out.print(temp.data + " ");
if (temp.leftChild != null) {
s1.push(temp.leftChild);
}
if (temp.rightChild != null) {
s1.push(temp.rightChild);
}
}
}
}
public void printSpiralReveerse(TreeBNode node) {
Stack s = new Stack<>();
Queue q = new LinkedList<>();
q.add(node);
while (q.isEmpty() == false) {
node = q.peek();
q.remove();
s.add(node);
if (node.rightChild != null) {
q.add(node.rightChild);
}
if (node.leftChild != null) {
q.add(node.leftChild);
}
}
while (s.isEmpty() == false) {
node = s.peek();
System.out.print(node.data + " ");
s.pop();
}
}
public void printZigZagTraversal(TreeBNode root) {
Stack s1 = new Stack<>();
Stack s2 = new Stack<>();
s1.push(root);
while (!s1.isEmpty() || !s2.isEmpty()) {
while (!s1.isEmpty()) {
TreeBNode temp = s1.peek();
System.out.print(temp.data + " ");
s1.pop();
if (temp.leftChild != null) {
s2.add(temp.leftChild);
}
if (temp.rightChild != null) {
s2.add(temp.rightChild);
}
}
while (!s2.isEmpty()) {
TreeBNode temp = s2.peek();
System.out.print(temp.data + " ");
s2.pop();
if (temp.rightChild != null) {
s1.add(temp.rightChild);
}
if (temp.leftChild != null) {
s1.add(temp.leftChild);
}
}
}
}
private static void printBoundary(TreeBNode rootNode) {
if(rootNode!=null){
printRoot(rootNode);
if(rootNode.getLeftChild()!=null)
printLeft(rootNode.getLeftChild());
printLeaf(rootNode);
if(rootNode.getRightChild()!=null)
printRight(rootNode.getRightChild());
}
}
private static void printRoot(TreeBNode rootNode) {
System.out.print(rootNode.getData() + " ");
}
private static void printLeft(TreeBNode rootNode){
if(rootNode==null){
return;
}
if(rootNode.getLeftChild()==null && rootNode.getRightChild()==null){
return;
}
System.out.print(rootNode.getData() + " ");
if(rootNode.getLeftChild()==null){
printLeft(rootNode.getRightChild());
}else{
printLeft(rootNode.getLeftChild());
}
}
private static void printLeaf(TreeBNode rootNode){
if(rootNode==null){
return;
}
if(rootNode.getLeftChild()==null && rootNode.getRightChild()==null){
System.out.print(rootNode.getData() + " ");
return;
}
printLeaf(rootNode.getLeftChild());
printLeaf(rootNode.getRightChild());
}
private static void printRight(TreeBNode rootNode){
if(rootNode==null){
return;
}
if(rootNode.getLeftChild()==null && rootNode.getRightChild()==null){
return;
}
if(rootNode.getRightChild()==null){
printRight(rootNode.getLeftChild());
System.out.print(rootNode.getData() + " ");
}else{
printRight(rootNode.getRightChild());
System.out.print(rootNode.getData() + " ");
}
}
public static void verticalTraversal(TreeBNode root, int distance){
if ( null == root){
return;
}
ArrayList list = null;
if(map.containsKey(distance)){
list = (ArrayList) map.get(distance);
}else{
list = new ArrayList();
}
list.add(root.data);
map.put(distance, list);
verticalTraversal(root.leftChild, distance-1);
verticalTraversal(root.rightChild, distance+1);
}
public static void main(String[] args) {
TreeBNode root = new TreeBNode(10);
root.leftChild = new TreeBNode(20);
root.rightChild = new TreeBNode(30);
root.leftChild.leftChild = new TreeBNode(40);
root.leftChild.rightChild = new TreeBNode(50);
root.rightChild.leftChild = new TreeBNode(60);
root.rightChild.rightChild = new TreeBNode(70);
System.out.println("------Preorder----");
preOrderTraversal(root);
System.out.println("");
System.out.println();
System.out.println("");
System.out.println("----------postOrder--------");
postOrderTraversal(root);
System.out.println();
System.out.println("---post without Rec");
postOrderWithoutRecu(root);
System.out.println("");
System.out.println("---In Order--");
inOrderTraversal(root);
System.out.println("");
System.out.println("---In Order REC---");
INOrderWithoutREC(root);
System.out.println(" ==== ");
inOrderIter(root);
System.out.println("");
System.out.println("Boundry");
printBoundary(root);
System.out.println("");
System.out.println("Vertical");
verticalTraversal(root, 0);
for(Map.Entry> entry: map.entrySet()){
System.out.println("Distance : "+entry.getKey() + " Nodes : "+entry.getValue());
}
}
}
Comments
Post a Comment