import java.util.*;
public class test {
static class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
static class BinaryTree {
static Node buildTree(Scanner scanner, String position, int parentValue) {
System.out.print("Add " + position + " node for " + parentValue + " (y/n): ");
String userChoice = scanner.next();
if (userChoice.equalsIgnoreCase("y")) {
System.out.print("Enter " + position + " node value: ");
int nodeValue = scanner.nextInt();
Node newNode = new Node(nodeValue);
newNode.left = buildTree(scanner, "left", nodeValue);
newNode.right = buildTree(scanner, "right", nodeValue);
return newNode;
} else {
return null;
}
}
}
//levelorder traversal
public static void levelorder(Node root)
{
if(root==null) return;
Queue<Node> q = new LinkedList<>();
q.add(root);
q.add(null);
while(!q.isEmpty())
{
Node currnode = q.remove();
if(currnode==null) //NULL DENOTES NEW LINE
{
System.out.println();
if(q.isEmpty())
{
break;
}
else
{
q.add(null);
}
}
else
{
System.out.print(currnode.data+" ");
if(currnode.left!=null)
{
q.add(currnode.left);
}
if(currnode.right!=null)
{
q.add(currnode.right);
}
}
}
}
public static ArrayList<Integer> preorderUsingStack(Node root)
{
ArrayList<Integer> preorderArrayList = new ArrayList<Integer>();
if (root==null) return preorderArrayList;
Stack<Node> st = new Stack<Node>();
st.push(root);
while(!st.isEmpty())
{
root = st.pop();
preorderArrayList.add(root.data);
if(root.right != null)
{
st.push(root.right);
}
if(root.left != null)
{
st.push(root.left);
}
}
return preorderArrayList;
}
public static ArrayList<Integer> inorderUsingStack(Node root)
{
ArrayList<Integer> inorderArrayList = new ArrayList<Integer>();
if (root == null) return null;
Stack<Node> st = new Stack<Node>();
Node node = root;
while(true)
{
if(node != null)
{
st.push(node);
node = node.left;
}
else
{
if(st.isEmpty())
{
break;
}
node = st.pop();
inorderArrayList.add(node.data);
node = node.right;
}
}
return inorderArrayList;
}
public static ArrayList<Integer> postorderUsing2Stack(Node root)
{
ArrayList<Integer> postorderArrayList = new ArrayList<Integer>();
if(root == null){return postorderArrayList;}
Stack<Node> st1 = new Stack<Node>();
Stack<Node> st2 = new Stack<Node>();
st1.push(root);
while(!st1.isEmpty())
{
root = st1.pop();
st2.push(root);
if(root.left!=null) st1.push(root.left);
if(root.right!=null) st1.push(root.right);
}
while(!st2.isEmpty())
{
postorderArrayList.add(st2.pop().data);
}
return postorderArrayList;
}
public static ArrayList<Integer> postorderUsing1Stack(Node root) {
ArrayList<Integer> postorderArrayList = new ArrayList<Integer>();
if (root == null) return postorderArrayList;
Stack<Node> st = new Stack<Node>();
Node curr = root;
Node prev = null;
while (curr != null || !st.isEmpty()) {
if (curr != null) {
st.push(curr);
curr = curr.left;
} else {
Node peekNode = st.peek();
if (peekNode.right == null || peekNode.right == prev) { //peekNode is topNode in stack
postorderArrayList.add(peekNode.data);
prev = peekNode;
st.pop();
} else {
curr = peekNode.right;
}
}
}
return postorderArrayList;
}
static class node_numOfTraversal_pair
{
Node node;
int num;
public node_numOfTraversal_pair(Node root, int _num)
{
this.num = _num;
this.node = root;
}
}
public static void preInPost_traversal_in_one(Node root, ArrayList<Integer> preorderArrayList, ArrayList<Integer> inorderArrayList, ArrayList<Integer> postorderArrayList)
{
Stack<node_numOfTraversal_pair> st = new Stack<node_numOfTraversal_pair>();
if(root == null) return;
// or instead pf above two lines you can directly write as below
// node_numOfTraversal_pair pair = new node_numOfTraversal_pair(root,1);
// st.push(pair);
st.push(new node_numOfTraversal_pair(root, 1));
while(!st.isEmpty())
{
node_numOfTraversal_pair it = st.pop();
// this is part of pre
// increment 1 to 2
// push the left side of the tree
if(it.num == 1)
{
preorderArrayList.add(it.node.data);
it.num++;
st.push(it);
if(it.node.left != null)
{
st.push(new node_numOfTraversal_pair(it.node.left, 1));
}
}
// this is a part of in
// increment 2 to 3
// push right
else if(it.num == 2)
{
inorderArrayList.add(it.node.data);
it.num++;
st.push(it);
if(it.node.right != null)
{
st.push(new node_numOfTraversal_pair(it.node.right, 1));
}
}
// don't push it back again
else
{
postorderArrayList.add(it.node.data);
}
}
}
public static int maxDepthOfBinaryTree(Node root)
{
if(root == null) return 0;
int leftHeight = maxDepthOfBinaryTree(root.left);
int rightHeight = maxDepthOfBinaryTree(root.right);
return 1 + Math.max(leftHeight,rightHeight);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
BinaryTree bt = new BinaryTree();
System.out.print("Enter root node value: ");
int rootValue = scanner.nextInt();
Node root = new Node(rootValue);
root.left = bt.buildTree(scanner, "left", rootValue);
root.right = bt.buildTree(scanner, "right", rootValue);
System.out.println("Tree construction complete.");
levelorder(root);
System.out.println(preorderUsingStack(root));
System.out.println(inorderUsingStack(root));
System.out.println(postorderUsing2Stack(root));
System.out.println(postorderUsing1Stack(root));
ArrayList<Integer> preorderArrayList = new ArrayList<Integer>();
ArrayList<Integer> inorderArrayList = new ArrayList<Integer>();
ArrayList<Integer> postorderArrayList = new ArrayList<Integer>();
preInPost_traversal_in_one(root, preorderArrayList, inorderArrayList, postorderArrayList);
System.out.print("The preorder traversal is: ");
for (Integer pre : preorderArrayList) {
System.out.print(pre+" ");
}
System.out.println();
System.out.print("The inorder traversal is: ");
for (Integer in : inorderArrayList) {
System.out.print(in+" ");
}
System.out.println();
System.out.print("The postorder traversal is: ");
for (Integer post : postorderArrayList) {
System.out.print(post+" ");
}
System.out.println();
System.out.println("The depth of your tree is: "+maxDepthOfBinaryTree(root));
scanner.close();
}
}
No comments:
Post a Comment