Binary tree to linked list using recursion,stack and morris traversal 9code in JAVA)
import java.util.*;
import javax.swing.tree.TreeNode;
public class test {
static class Node {
int data;
Node left;
Node right;
int hd;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
hd = 0;
}
}
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 of 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);
}
// To check for Balanced Binary Tree
public static int isBalacedBinaryTree(Node root)
{
if(root == null) return 0;
int leftHeight = isBalacedBinaryTree(root.left);
if(leftHeight==-1){return -1;}
int rightHeight = isBalacedBinaryTree(root.right);
if(rightHeight==-1){return -1;}
if(Math.abs(leftHeight-rightHeight)>1){return -1;}
return 1 + Math.max(leftHeight,rightHeight);
}
public static boolean isBalancedBinaryTree_boolean_value(Node root)
{
return isBalacedBinaryTree(root) != -1;
}
// To measure diameter of binary tree
public static int height(Node root, int diameter[])
{
if(root == null) return 0;
int leftHeight = height(root.left,diameter);
int rightHeight = height(root.right,diameter);
diameter[0] = Math.max(diameter[0],leftHeight+rightHeight);
return 1 + Math.max(leftHeight,rightHeight);
}
public static int diameterofbinarytree(Node root)
{
int diameter1[]= new int[1];
height(root,diameter1);
return diameter1[0];
}
// Maximum Path Sum
public static int maxPath(Node node, int maxValue[]) {
if (node == null) return 0;
int left = Math.max(0, maxPath(node.left, maxValue));
int right = Math.max(0, maxPath(node.right, maxValue));
maxValue[0] = Math.max(maxValue[0], left + right + node.data);
return Math.max(left, right) + node.data;
}
public static int maxPathSum(Node root) {
int maxValue[] = new int[1];
maxValue[0] = Integer.MIN_VALUE;
maxPath(root, maxValue);
return maxValue[0];
}
// Zig-zag or spiral traversal
static ArrayList<Integer> zigZagTraversal(Node root)
{
ArrayList<Integer> ans = new ArrayList<Integer>();
if (root == null)
return ans;
Queue<Node> q = new LinkedList<Node>();
q.add(root);
boolean leftToRight = true;
while (q.size() > 0) {
int size = q.size();
ArrayList<Integer> temp = new ArrayList<>();
for (int i = 0; i < size; i++) {
Node curr = q.poll();
if (curr.left != null)
q.add(curr.left);
if (curr.right != null)
q.add(curr.right);
temp.add(curr.data);
}
if (leftToRight)
{
// do nothing
}
else {
Collections.reverse(temp);
}
for (int i = 0; i < temp.size(); i++) {
ans.add(temp.get(i));
}
leftToRight = !(leftToRight);
}
return ans;
}
// boundary traversal
public static void printLeftBoundary(Node node) {
if (node == null)
return;
if (node.left != null) {
System.out.print(node.data + " ");
printLeftBoundary(node.left);
} else if (node.right != null) {
System.out.print(node.data + " ");
printLeftBoundary(node.right);
}
}
public static void printRightBoundary(Node node) {
if (node == null)
return;
if (node.right != null) {
printRightBoundary(node.right);
System.out.print(node.data + " ");
} else if (node.left != null) {
printRightBoundary(node.left);
System.out.print(node.data + " ");
}
}
public static void printLeaves(Node node) {
if (node == null)
return;
printLeaves(node.left);
if (node.left == null && node.right == null)
System.out.print(node.data + " ");
printLeaves(node.right);
}
public static void boundaryTraversal(Node root) {
if (root == null)
return;
System.out.print(root.data + " ");
printLeftBoundary(root.left);
printLeaves(root.left);
printLeaves(root.right);
printRightBoundary(root.right);
}
// Vertical order traversal
public static void verticalOrder(Node root,int horizontal_dist, Map<Integer, Vector<Integer>> m)
{
if (root==null) return;
Vector<Integer> v = m.get(horizontal_dist);
if(v==null)
{
v = new Vector<Integer>();
v.add(root.data);
}
else
{
v.add(root.data);
}
m.put(horizontal_dist,v);
verticalOrder(root.left, horizontal_dist - 1, m);
verticalOrder(root.right, horizontal_dist + 1, m);
}
// Top-view of a binary tree
public static class Pair {
Node node;
int hd;
Pair(Node node, int hd) {
this.node = node;
this.hd = hd;
}
}
static ArrayList<Integer> topView(Node root)
{
ArrayList<Integer> ans = new ArrayList<>();
if(root == null) return ans;
Map<Integer, Integer> map = new TreeMap<>();
Queue<Pair> q = new LinkedList<Pair>();
q.add(new Pair(root, 0));
while(!q.isEmpty()) {
Pair it = q.remove();
int hd = it.hd;
Node temp = it.node;
if(map.get(hd) == null) map.put(hd, temp.data);
if(temp.left != null) {
q.add(new Pair(temp.left, hd - 1));
}
if(temp.right != null) {
q.add(new Pair(temp.right, hd + 1));
}
}
for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
ans.add(entry.getValue());
}
return ans;
}
// Bottom-View of Binary Tree
public static ArrayList <Integer> bottomView(Node root)
{
ArrayList<Integer> ans = new ArrayList<>();
if(root == null) return ans;
Map<Integer, Integer> map = new TreeMap<>();
Queue<Node> q = new LinkedList<Node>();
root.hd = 0;
q.add(root);
while(!q.isEmpty()) {
Node temp = q.remove();
int hd = temp.hd;
map.put(hd, temp.data);
if(temp.left != null) {
temp.left.hd = hd - 1;
q.add(temp.left);
}
if(temp.right != null) {
temp.right.hd = hd + 1;
q.add(temp.right);
}
}
for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
ans.add(entry.getValue());
}
return ans;
}
// Right View of binary tree
public static List<Integer> rightSideView(Node root) {
List<Integer> result = new ArrayList<Integer>();
rightView(root, result, 0);
return result;
}
public static void rightView(Node curr, List<Integer> result, int currDepth){
if(curr == null){
return;
}
if(currDepth == result.size()){
result.add(curr.data);
}
rightView(curr.right, result, currDepth + 1);
rightView(curr.left, result, currDepth + 1);
}
//Left-side view
public static List<Integer> leftSideView(Node root) {
List<Integer> result = new ArrayList<Integer>();
leftView(root, result, 0);
return result;
}
public static void leftView(Node curr, List<Integer> result, int currDepth){
if(curr == null){
return;
}
if(currDepth == result.size()){
result.add(curr.data);
}
leftView(curr.left, result, currDepth + 1);
leftView(curr.right, result, currDepth + 1);
}
// Check if bianry tree is symmetric or not
static boolean isSymmetricUtil(Node root1, Node root2) {
if (root1 == null || root2 == null)
return root1 == root2;
return (root1 . data == root2 . data) && isSymmetricUtil(root1 . left, root2 .
right) && isSymmetricUtil(root1 . right, root2 . left);
}
static boolean isSymmetric(Node root) {
if (root==null) return true;
return isSymmetricUtil(root . left, root . right);
}
// Print root to node path
static boolean getPath(Node root, ArrayList < Integer > arr, int x) {
if (root == null)
return false;
arr.add(root.data);
if (root.data == x)
return true;
if (getPath(root.left, arr, x) ||
getPath(root.right, arr, x))
return true;
arr.remove(arr.size() - 1);
return false;
}
public static void printPath(Node root, int node_data)
{
ArrayList < Integer > arr = new ArrayList < > ();
boolean res;
res = getPath(root, arr, node_data);
System.out.print("The Root to node path is: ");
for (int it: arr) {
System.out.print(it + " ");
}
}
// lowest common ancestor of binary tree
public static Node lowestCommonAncestor(Node root, Node p, Node q) {
if (root == null || root == p || root == q) {
return root;
}
Node left = lowestCommonAncestor(root.left, p, q);
Node right = lowestCommonAncestor(root.right, p, q);
//result
if(left == null) {
return right;
}
else if(right == null) {
return left;
}
else { //both left and right are not null, we found our result
return root;
}
}
// Maximum width of a binary tree
public static int widthOfBinaryTree(Node root) {
if(root == null) return 0;
int ans = 0;
Queue<Pair> q = new LinkedList<>();
q.offer(new Pair(root, 0));
while(!q.isEmpty()){
int size = q.size();
int mmin = q.peek().hd; //to make the id starting from zero
int first = 0,last = 0; //hd code written in Pair class
for(int i=0; i<size; i++){
int cur_id = q.peek().hd-mmin;
Node node = q.peek().node;
q.poll();
if(i==0) first = cur_id;
if(i==size-1) last = cur_id;
if(node.left != null)
q.offer(new Pair(node.left, cur_id*2+1));
if(node.right != null)
q.offer(new Pair(node.right, cur_id*2+2));
}
ans = Math.max(ans, last-first+1);
}
return ans;
}
//Children sum property in binary tree
static void reorder(Node root) {
if (root == null) return;
int child = 0;
if (root . left!=null) {
child += root . left . data;
}
if (root . right!=null) {
child += root . right . data;
}
if (child < root . data) {
if (root . left!=null) root . left . data = root . data;
else if (root . right!=null) root . right . data = root . data;
}
reorder(root . left);
reorder(root . right);
int tot = 0;
if (root . left!=null) tot += root . left . data;
if (root . right!=null) tot += root . right . data;
if (root . left!=null || root . right!=null) root . data = tot;
}
static void changeTree(Node root) {
reorder(root);
}
//print nodes at distance k
static void printkdistanceNodeDown(Node node, int k)
{
// Base Case
if (node == null || k < 0)
return;
// If we reach a k distant node, print it
if (k == 0)
{
System.out.print(node.data);
System.out.println("");
return;
}
// Recur for left and right subtrees
printkdistanceNodeDown(node.left, k - 1);
printkdistanceNodeDown(node.right, k - 1);
}
// Prints all nodes at distance k from a given target node.
// The k distant nodes may be upward or downward.This function
// Returns distance of root from target node, it returns -1
// if target node is not present in tree rooted with root.
static int printkdistanceNode(Node node, Node target, int k)
{
// Base Case 1: If tree is empty, return -1
if (node == null)
return -1;
// If target is same as root. Use the downward function
// to print all nodes at distance k in subtree rooted with
// target or root
if (node == target)
{
printkdistanceNodeDown(node, k);
return 0;
}
// Recur for left subtree
int dl = printkdistanceNode(node.left, target, k);
// Check if target node was found in left subtree
if (dl != -1)
{
// If root is at distance k from target, print root
// Note that dl is Distance of root's left child from
// target
if (dl + 1 == k)
{
System.out.print(node.data);
System.out.println("");
}
// Else go to right subtree and print all k-dl-2 distant nodes
// Note that the right child is 2 edges away from left child
else
printkdistanceNodeDown(node.right, k - dl - 2);
// Add 1 to the distance and return value for parent calls
return 1 + dl;
}
// MIRROR OF ABOVE CODE FOR RIGHT SUBTREE
// Note that we reach here only when node was not found in left
// subtree
int dr = printkdistanceNode(node.right, target, k);
if (dr != -1)
{
if (dr + 1 == k)
{
System.out.print(node.data);
System.out.println("");
}
else
printkdistanceNodeDown(node.left, k - dr - 2);
return 1 + dr;
}
// If target was neither present in left nor in right subtree
return -1;
}
//count total number of nodes in complete binary tree
static void inOrderTrav(Node curr, int count[]) {
if (curr == null)
return;
count[0]++;
inOrderTrav(curr . left, count);
inOrderTrav(curr . right, count);
}
// Serialise and De-Serialise
public static String serialize(Node root) {
if (root == null) return "";
Queue<Node> q = new LinkedList<>();
StringBuilder res = new StringBuilder();
q.add(root);
while (!q.isEmpty()) {
Node node = q.poll();
if (node == null) {
res.append("n ");
continue;
}
res.append(node.data + " ");
q.add(node.left);
q.add(node.right);
}
return res.toString();
}
public static Node deserialize(String data) {
if (data == "") return null;
Queue<Node> q = new LinkedList<>();
String[] values = data.split(" ");
Node root = new Node(Integer.parseInt(values[0]));
q.add(root);
for (int i = 1; i < values.length; i++) {
Node parent = q.poll();
if (!values[i].equals("n")) {
Node left = new Node(Integer.parseInt(values[i]));
parent.left = left;
q.add(left);
}
if (!values[++i].equals("n")) {
Node right = new Node(Integer.parseInt(values[i]));
parent.right = right;
q.add(right);
}
}
return root;
}
//Morris inorder traversal of a binary tree
public static List<Integer> MorrisInorderTraversal(Node root) {
List<Integer> inorder = new ArrayList<Integer>();
Node cur = root;
while(cur != null) {
if(cur.left == null) {
inorder.add(cur.data);
cur = cur.right;
}
else {
Node prev = cur.left;
while(prev.right != null && prev.right != cur) {
prev = prev.right;
}
if(prev.right == null) {
prev.right = cur;
cur = cur.left;
}
else {
prev.right = null;
inorder.add(cur.data);
cur = cur.right;
}
}
}
return inorder;
}
//Morris preorder traversal of a binary tree
public static ArrayList < Integer > MorrisPreorderTraversal(Node root) {
ArrayList < Integer > preorder = new ArrayList < > ();
Node cur = root;
while (cur != null) {
if (cur.left == null) {
preorder.add(cur.data);
cur = cur.right;
} else {
Node prev = cur.left;
while (prev.right != null && prev.right != cur) {
prev = prev.right;
}
if (prev.right == null) {
prev.right = cur;
preorder.add(cur.data);
cur = cur.left;
} else {
prev.right = null;
cur = cur.right;
}
}
}
return preorder;
}
//Flatten Binary Tree to Linked List
// using recursion
static Node prev = null;
static void flatten(Node root) {
if (root == null) return;
flatten(root . right);
flatten(root . left);
root . right = prev;
root . left = null;
prev = root;
}
public static void BinaryToLinkedList_recursion(Node root)
{
flatten(root);
while(root.right!=null)
{
System.out.print(root.data+"->");
root=root.right;
}
System.out.print(root.data);
}
//using stack and using morris traversal are also there the code is commented
/*
using stack
static Node prev = null;
static void flatten(Node root) {
if (root == null) return;
Stack < Node > st=new Stack<>();
st.push(root);
while (!st.isEmpty()) {
Node cur = st.peek();
st.pop();
if (cur . right != null) {
st.push(cur . right);
}
if (cur . left != null) {
st.push(cur . left);
}
if (!st.isEmpty()) {
cur . right = st.peek();
}
cur . left = null;
}
}
// using morris travesal
static Node prev = null;
static void flatten(Node root) {
Node cur = root;
while (cur!=null)
{
if(cur.left!=null)
{
Node pre = cur.left;
while(pre.right!=null)
{
pre = pre.right;
}
pre.right = cur.right;
cur.right = cur.left;
cur.left = null;
}
cur = cur.right;
}
}
*/
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));
boolean balanced_var = isBalancedBinaryTree_boolean_value(root);
System.out.println(balanced_var);
System.out.println("The diameter of given binary tree is: "+diameterofbinarytree(root));
System.out.println("The maximum path sum is: "+maxPathSum(root));
System.out.println("The zigZag Traversal is: "+zigZagTraversal(root));
System.out.println("The boundary traversal is as below:");
boundaryTraversal(root);
System.out.println();
System.out.println("The vertical order traversal is as below:");
TreeMap<Integer, Vector<Integer>> m = new TreeMap<>();
int hd = 0;
verticalOrder(root, hd, m);
for (Map.Entry<Integer,Vector<Integer>> e : m.entrySet()) {
System.out.println(e.getValue());
}
System.out.println("Top view traversal is :");
System.out.println(topView(root));
System.out.println("Bottom view traversal is :");
System.out.println(bottomView(root));
System.out.println("The right-side view is:");
System.out.println(rightSideView(root));
System.out.println("The left-side view is:");
System.out.println(leftSideView(root));
System.out.println("The binary tree is symmetric: "+isSymmetric(root));
printPath(root, 7);
System.out.println();
//System.out.println("The lowest common ancestor is: "+lowestCommonAncestor(root, root.left.left, root.left.right.right).data);
System.out.println("The maximum width of a binary tree is: "+widthOfBinaryTree(root));
//System.out.println("Level order traversal of tree after children sum property is: ");
//changeTree(root);
//levelorder(root);
//System.out.println("The nodes at distance k is: ");
//Node target = root.left.right;
//printkdistanceNode(root, target, 2);
//System.out.println("--");
int count[]=new int[1];
inOrderTrav(root, count);
System.out.println("The total number of nodes in the given complete binary tree are: "+count[0]);
System.out.println(serialize(root));
System.out.println(deserialize(serialize(root)).data);
System.out.println(MorrisInorderTraversal(root));
System.out.println(MorrisPreorderTraversal(root));
BinaryToLinkedList_recursion(root);
scanner.close();
}
}
No comments:
Post a Comment