import java.util.*;
public class BTreeTraversal {
public static void main(String... args) {
int[] values = {10, 5, 20, 3, 15, 7, 26, 9, 14};
System.out.println("inserting order");
for(int i = 0; i < values.length; i++) {
System.out.print(values[i] + " ");
}
System.out.println();
BTree root = buildTree(values);
System.out.println("LayerOrderWithLineBreak");
LayerOrderWithLineBreak(root);
System.out.println();
System.out.println("RevLayerOrderWithLineBreak");
RevLayerOrderWithLineBreak(root);
System.out.println();
System.out.println("LayerOrder");
LayerOrder(root);
System.out.println();
System.out.println("LayerOrder2");
LayerOrder2(root);
System.out.println();
System.out.println("InOrder");
InOrder(root);
System.out.println();
System.out.println("InOrder2");
InOrder2(root);
System.out.println();
System.out.println("PreOrder");
PreOrder(root);
System.out.println();
System.out.println("PostOrder");
PostOrder(root);
System.out.println();
System.out.println("height of the tree");
System.out.println(height(root));
System.out.println("min node of the tree");
System.out.println(min(root));
System.out.println("max node of the tree");
System.out.println(max(root));
}
//build a binary search tree
public static BTree buildTree(int[] values) {
BTree root = null;
for(int value : values) {
root = insert(root, value);
}
return root;
}
public static BTree insert(BTree root, int value) {
if(root == null) {
return new BTree(value, null, null);
}
if(value > root.value) {
root.right = insert(root.right, value);
return root;
}
if(value < root.value) {
root.left = insert(root.left, value);
return root;
}
root.value = value;
return root;
}
//print a binary search tree from top down, left to right
public static void LayerOrder(BTree root) {
if(root == null) return;
Queue<BTree> queue = new LinkedList<>();
queue.offer(root);
BTree current = null;
while(!queue.isEmpty()) {
current = queue.poll();
System.out.print(current.value + " ");
if(current.left != null)
queue.offer(current.left);
if(current.right != null)
queue.offer(current.right);
}
}
//print a binary search tree from top down, right to left
public static void LayerOrder2(BTree root) {
if(root == null) return;
Queue<BTree> queue = new LinkedList<>();
queue.offer(root);
BTree current = null;
while(!queue.isEmpty()) {
current = queue.poll();
System.out.print(current.value + " ");
if(current.right != null)
queue.offer(current.right);
if(current.left != null)
queue.offer(current.left);
}
}
/* line by line print level order traversal a tree with line breaks*/
public static void LayerOrderWithLineBreak(BTree root)
{
int h = height(root);
int i;
for (i=1; i<=h; i++)
{
printGivenLevel(root, i);
System.out.println();
}
}
/* line by line print reverse level order traversal a tree with line breaks*/
public static void RevLayerOrderWithLineBreak(BTree root)
{
int h = height(root);
int i;
for (i=h; i>=1; i--)
{
printGivenLevel(root, i);
System.out.println();
}
}
/* Print nodes at a given level */
public static void printGivenLevel(BTree root, int level)
{
if (root == null)
return;
if (level == 1)
System.out.print(root.value + " ");
else if (level > 1)
{
printGivenLevel(root.left, level-1);
printGivenLevel(root.right, level-1);
}
}
//calculate the height of a binary search tree
public static int height(BTree root) {
if(root == null)
return 0;
int leftHeight = height(root.left);
int rightHeight = height(root.right);
return leftHeight >= rightHeight ? leftHeight + 1 : rightHeight + 1;
}
//print in order traversal a tree
//print tree element sorted small to large
public static void InOrder(BTree root) {
if(root == null) {
return;
}
InOrder(root.left);
System.out.print(root.value + " ");
InOrder(root.right);
}
//print tree element sorted large to small
public static void InOrder2(BTree root) {
if(root == null) {
return;
}
InOrder2(root.right);
System.out.print(root.value + " ");
InOrder2(root.left);
}
//print pre order traversal a tree
public static void PreOrder(BTree root) {
if(root == null) {
return;
}
System.out.print(root.value + " ");
PreOrder(root.left);
PreOrder(root.right);
}
//print post order traversal a tree
public static void PostOrder(BTree root) {
if(root == null) {
return;
}
PostOrder(root.left);
PostOrder(root.right);
System.out.print(root.value + " ");
}
//get the min node of a tree
public static BTree min(BTree root) {
if(root == null) return null;
while(root.left != null) {
root = root.left;
}
return root;
}
//get the max node of a tree
public static BTree max(BTree root) {
if(root == null) return null;
while(root.right != null) {
root = root.right;
}
return root;
}
}
