/*Tree Operations
LevelOrder
Spiral
SpiralReverse
TopView
BottomeView
Mirror
Identical
HeightOfTree
HeightOfTree
zigzag*/
import java.util.LinkedList;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Queue;
import java.util.Stack;
import java.util.TreeMap;
class TreeBNode {
int data;
TreeBNode leftChild;
TreeBNode rightChild;
boolean visited;
public TreeBNode(int data) {
this.data = data;
this.leftChild = null;
this.rightChild = null;
this.visited =false;
}
}
class QueueObj {
TreeBNode node;
int hd;
public QueueObj(TreeBNode node, int hd) {
this.node = node;
this.hd = hd;
// TODO Auto-generated constructor stub
}
}
public class AllTreeOperations {
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 printTopView(TreeBNode root) {
Queue q = new LinkedList();
Map map = new TreeMap();
if (root == null) {
return;
}
else {
q.add(new QueueObj(root, 0));
}
while (!q.isEmpty()) {
QueueObj temp = q.poll();
if (!map.containsKey(temp.hd)) {
map.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));
}
}
for (Entry entry : map.entrySet()) {
System.out.print(entry.getValue().data + " ");
}
}
public int printHeightOfTheTree(TreeBNode root) {
int rightCount = 0;
int leftCount = 0;
Stack s = new Stack<>();
Stack s1 = new Stack<>();
s.push(root);
s1.push(root);
while (!s.isEmpty()) {
TreeBNode temp = s.peek();
s.pop();
leftCount++;
if (temp.leftChild != null) {
s.push(temp.leftChild);
}
}
while (!s1.isEmpty()) {
TreeBNode temp1 = s1.peek();
s1.pop();
rightCount++;
if (temp1.rightChild != null) {
s1.push(temp1.rightChild);
}
}
if (leftCount > rightCount) {
return leftCount - 1;
}
else {
return rightCount - 1;
}
}
public boolean areMirror(TreeBNode root1, TreeBNode root2) {
Stack s = new Stack();
Queue q = new LinkedList<>();
s.push(root1);
q.add(root2);
while (!s.isEmpty() || !q.isEmpty()) {
while (!s.isEmpty()) {
TreeBNode temp1 = s.peek();
System.out.print(temp1.data + " ");
s.pop();
if (temp1.leftChild != null) {
s.push(temp1.leftChild);
}
if (temp1.rightChild != null) {
s.push(temp1.rightChild);
}
}
while (!q.isEmpty()) {
TreeBNode temp2 = q.peek();
System.out.print(temp2.data + " --");
q.remove();
if (temp2.leftChild != null) {
q.add(temp2.leftChild);
}
if (temp2.rightChild != null) {
q.add(temp2.rightChild);
}
}
}
if (s.equals(q)) {
return true;
}
return false;
}
public boolean areIdentical(TreeBNode root1, TreeBNode root2) {
Queue q1 = new LinkedList<>();
Queue q2 = new LinkedList<>();
q1.add(root1);
q2.add(root2);
while (!q1.isEmpty() || !q2.isEmpty()) {
while (!q1.isEmpty()) {
TreeBNode temp1 = q1.peek();
System.out.print(temp1.data + " ");
q1.remove();
if (temp1.leftChild != null) {
q1.add(temp1.leftChild);
}
if (temp1.rightChild != null) {
q1.add(temp1.rightChild);
}
}
System.out.println();
while (!q2.isEmpty()) {
TreeBNode temp2 = q2.peek();
System.out.print(temp2.data + "--");
q2.remove();
if (temp2.leftChild != null) {
q2.add(temp2.leftChild);
}
if (temp2.rightChild != null) {
q2.add(temp2.rightChild);
}
}
}
if (q1.equals(q2)) {
return true;
}
return false;
}
public void printBottomView(TreeBNode root) {
if (root == null)
return;
int hd = 0;
Map map = new TreeMap<>();
Queue queue = new LinkedList();
queue.add(new QueueObj(root, 0));
while (!queue.isEmpty()) {
QueueObj temp = queue.poll();
// if we use below condition then it is top view else bottom view
// if(!map.containsKey(temp.hd)) {
map.put(temp.hd, temp.node);
// }
if (temp.node.leftChild != null) {
queue.add(new QueueObj(temp.node.leftChild, temp.hd - 1));
}
if (temp.node.rightChild != null) {
queue.add(new QueueObj(temp.node.rightChild, temp.hd + 1));
}
}
for (Entry entry : map.entrySet()) {
System.out.print(entry.getValue().data + " ");
}
}
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);
}
}
}
}
public static void main(String[] args) {
TreeBNode root = new TreeBNode(10);
root.leftChild = new TreeBNode(20);
root.rightChild = new TreeBNode(30);
}
}
Comments
Post a Comment