Full Tree

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Stack;
import java.util.TreeMap;

public class FullTree {
public static void preOrder(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 (null != temp.rightChild) {
s.push(temp.rightChild);
}
if (null != temp.leftChild) {
s.push(temp.leftChild);
}
}
}
}

public static void InorderTr(TreeBNode root) {
if (null == root) {
return;
} else {
Stack s = new Stack<>();
boolean isVisited = false;
TreeBNode current = root;
while (!isVisited) {
if (null != current) {
s.push(current);
current = current.leftChild;
} else {
if (s.isEmpty()) {
isVisited = true;
} else {
current = s.pop();
System.out.print(current.data + " ");
current = current.rightChild;
}
}
}
}
}

public static void postOrderTr(TreeBNode root) {

Stack s = new Stack<>();
Stack s1 = new Stack<>();
s.push(root);
if (null == root) {
return;
} else {
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 levelOrderTr(TreeBNode root) {

Queue q = new LinkedList();
if (null == root) {
return;
} else {
q.offer(root);
while (!q.isEmpty()) {
TreeBNode temp = q.poll();
System.out.print(temp.data + " ");

if (null != temp.leftChild) {
q.offer(temp.leftChild);
}
if (null != temp.rightChild) {
q.offer(temp.rightChild);
}
}
}
}

public static void topView(TreeBNode root) {

Queue q = new LinkedList<>();
Map m = new HashMap<>();
q.add(new QueueObj(root, 0));
while (!q.isEmpty()) {
QueueObj temp = q.poll();
if (!m.containsKey(temp.hd)) {
m.put(temp.hd, temp.node);
}

if (temp.node.leftChild != null) {
q.add(new QueueObj(temp.node.leftChild, temp.hd - 1));
}
if (temp.node.rightChild != null) {
q.add(new QueueObj(temp.node.rightChild, temp.hd - 1));
}
}

}

public static void countLeaf(TreeBNode root) {
int count = 0;
Queue queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeBNode node = queue.poll();

if (node.rightChild == null && node.leftChild == null) {
count++;
System.out.print(node.data + " ");
} // else{
if (null != node.leftChild) {
queue.offer(node.leftChild);
}
if (null != node.rightChild) {
queue.offer(node.rightChild);
}
// }

}
// System.out.println(count);
// return count;
}

public static void getLeftNodes(TreeBNode root) {
int count = 0;
Queue queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeBNode node = queue.poll();

if (node.leftChild != null && node.rightChild != null) {
count++;
System.out.print(node.data + " ");
}
if (null != node.leftChild) {
queue.offer(node.leftChild);
}
}
// System.out.println(count);

}

public static void getRightNodes(TreeBNode root) {
int count = 0;
Queue queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeBNode node = queue.poll();

if (node.leftChild != null && node.rightChild != null) {
count++;
System.out.print(node.data + " ");
}
/*
* if(null!=node.leftChild ){ queue.offer(node.leftChild); }
*/
if (null != node.rightChild) {
queue.offer(node.rightChild);
}

}
// System.out.println(count);
// return count;

}

public static void getRoots(TreeBNode root) {
int count = 0;
Queue queue = new LinkedList();
queue.offer(root);
while (!queue.isEmpty()) {
TreeBNode node = queue.poll();
if (node.leftChild != null && node.rightChild != null) {
count++;
System.out.print(node.data + " ");
}
if (node.leftChild != null) {
queue.offer(node.leftChild);
}
if (node.rightChild != null) {
queue.offer(node.rightChild);
}

}
System.out.println(count);
// return count;
}

public static void postLeft(TreeBNode root) {

Stack s = new Stack<>();
Stack s1 = new Stack<>();
s.push(root);
if (null == root) {
return;
} else {
while (!s.isEmpty()) {
TreeBNode temp = s.pop();
s1.push(temp);
if (temp.leftChild != null) {
s.push(temp.leftChild);
}
System.out.print(temp.data + " ");
/*
* if (temp.rightChild != null) { s.push(temp.rightChild); }
*/

}
/*
* while (!s1.isEmpty()) { System.out.print(s1.pop().data + " "); }
*/
}
}

public static void boundryTra(TreeBNode root) {
if (root.leftChild != null) {
getLeftNodes(root);
}
countLeaf(root);
if (root.rightChild != null) {
getRightNodes(root);
}
}

public static TreeBNode lcaOfBT(TreeBNode root, int node1, int node2) {
if (null == root) {
return null;
}
if (root.data == node1 && root.data == node2) {
return root;
}
TreeBNode left = lcaOfBT(root.leftChild, node1, node2);
TreeBNode right = lcaOfBT(root.rightChild, node1, node2);
return left == null ? right : right == null ? left : root;
}

public static TreeBNode lcaOfBST(TreeBNode root, int node1, int node2) {

return ((root.data - node1) * (root.data - node2) < 1 ? root
: lcaOfBST(node1 < root.data ? root.leftChild : root.rightChild, node1, node2));
}

public static void spiralOrderTr(TreeBNode root) {

Stack s = new Stack<>();
Stack s1 = new Stack<>();
s.push(root);
while (!s.isEmpty() || !s1.isEmpty()) {
while (!s.isEmpty()) {
TreeBNode temp = s.pop();
System.out.print(temp.data + " ");
if (temp.rightChild != null) {
s1.push(temp.rightChild);
}
if (temp.leftChild != null) {
s1.push(temp.leftChild);
}

}
while (!s1.isEmpty()) {
TreeBNode temp = s1.pop();
System.out.print(temp.data + " ");
if (temp.leftChild != null) {
s.push(temp.leftChild);
}
if (temp.rightChild != null) {
s.push(temp.rightChild);
}
}
}
}

public static void bottomView(TreeBNode root) {

if (null == root) {
return;
}
int hd = 0;
Queue q = new LinkedList<>();
Map m = new TreeMap<>();

q.offer(new QueueObj(root, hd));
while (!q.isEmpty()) {
QueueObj qobj = q.poll();
m.put(qobj.hd, qobj.node);
if (qobj.node.leftChild != null) {
q.offer(new QueueObj(root, hd - 1));
}
if (qobj.node.rightChild != null) {
q.offer(new QueueObj(root, hd + 1));
}
}

for (Map.Entry e : m.entrySet()) {
System.out.print(e.getValue() + " ");
}

}

public static Boolean findElement(TreeBNode root, int n) {
if (null == root) {
return false;
}
Queue q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
TreeBNode temp = q.poll();
if (temp.data == n) {
return true;
}
if (null != temp.rightChild) {
q.offer(temp.rightChild);

}
if (null != temp.leftChild) {
q.offer(temp.leftChild);
}
}
return false;
}

public static void main(String[] args) {
// TODO Auto-generated method stub

}

}

class QueueObj1 {
TreeBNode node;
int hd;

public QueueObj1(TreeBNode node, int hd) {
this.node = node;
this.hd = hd;
}
}