Saturday, 23 September 2023

Insert  a given node Into BST (code 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;

}

    }


     */


    // Binary Search Tree (BST)

    // SEARCH IN BST

    public static Node searchBST(Node root, int val) {

        if (root == null || root.data == val) {

            return root;

        }


        if (val < root.data) {

            return searchBST(root.left, val);

        }


        return searchBST(root.right, val);

    }


    public static void printsearchBST(Node root,int target)

    {

        root = searchBST(root, target);

        if (root != null) {

            System.out.println(target + " found in the BST.");

        } else {

            System.out.println(target + " not found in the BST.");

        }

    }


    // CEIL IN BST

    public static int findCeil(Node root,int key)

    {

        int ceil = -1;

        while(root!=null)

        {

            if(root.data==key)

            {

                ceil = root.data;

                return ceil;

            }

            if(key>root.data)

            {

                root=root.right;

            }

            else

            {

                ceil=root.data;

                root=root.left;

            }

        }

        return ceil;

    }


    // Insert node in BST

    public static Node insertIntoBST(Node root,int val)

    {

        if(root==null) return new Node(val);

        Node cur = root;

        while(true)

        {

            if(cur.data<=val)

            {

                if(cur.right!=null) cur=cur.right;

                else{

                    cur.right=new Node(val);

                    break;

                }

            }

            else{

                

                if(cur.left!=null) cur=cur.left;

                else{

                    cur.left=new Node(val);

                    break;

                }

            }

        }

        return root;

    }

    

    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);

        printsearchBST(root, 8);

        System.out.println(findCeil(root, 4));

        insertIntoBST(root, 0);

        levelorder(root);

        scanner.close();

    }

}



  

No comments:

Post a Comment

Good thoughtful question on Binary search on answers

Problem link:  https://leetcode.com/problems/maximize-score-of-numbers-in-ranges/description/ Solution: //import java.util.Arrays; class So...