Question

Needed in Java Code

Create a Binary Search Tree with the following elements in the order mentioned below: 5, 85, 89, 3, 2, 8, 65, 92

1.Print the Pre-order of this tree

2. Print the height and the balance factor of the nodes in the order they were inserted (5, 85, 89, 3, 2, 8, 65, 92) in the form of a table with three columns and 9 rows. Use column headers “Node”, “Height”, and “Balance Factor” for the three columns respectively. Use the following table as reference for your output. Don't worry about printing the table borders. Note: You are not balancing the tree. You are just computing the heights and balance factors of a BST.

Answer 1

If you have doubts please comment don't dislike.

public class BinarySearchTree {
   public static Node root;
   public BinarySearchTree(){
       this.root = null;
   }
  
   public void insert(int id){
       Node newNode = new Node(id);
       if(root==null){
           root = newNode;
           return;
       }
       Node current = root;
       Node parent = null;
       while(true){
           parent = current;
           if(id<current.data){              
               current = current.left;
               if(current==null){
                   parent.left = newNode;
                   return;
               }
           }else{
               current = current.right;
               if(current==null){
                   parent.right = newNode;
                   return;
               }
           }
       }
   }
   public void preorder(Node root){
       if(root!=null){
           System.out.print(" " + root.data);
           preorder(root.left);
           preorder(root.right);
       }
   }
   public int getNodeHeight(Node root, int x, int height){
       if(root==null) return 0;
       if(root.data==x) return height;
      
       //check if the node is present in the left sub tree
       int level = getNodeHeight(root.left,x,height+1);
       //System.out.println(level);
       if(level!=0) return level;
      
       //check if the node is present in the right sub tree
       return getNodeHeight(root.right,x,height+1);
   }
   public int balancefactor(int x){
       if(root==null) return 0;
       return getNodeHeight(root.left,x,0)-getNodeHeight(root.right,x,0);
   }
   public static void main(String arg[]){
       BinarySearchTree b = new BinarySearchTree();
       b.insert(5);b.insert(85);
       b.insert(89);b.insert(3);b.insert(2);b.insert(8);b.insert(65);b.insert(92);
       System.out.println("Preorder Tree Traversal: ");
       b.preorder(b.root);      
       System.out.println("");
       System.out.println("Node Height balancefactor");
       System.out.println("5     "+b.getNodeHeight(root,5,0)+"   "+b.balancefactor(5));
       System.out.println("85    "+b.getNodeHeight(root,85,0)+" "+b.balancefactor(85));
       System.out.println("89    "+b.getNodeHeight(root,89,0)+" "+b.balancefactor(89));
       System.out.println("3     "+b.getNodeHeight(root,3,0)+"   "+b.balancefactor(3));
       System.out.println("2     "+b.getNodeHeight(root,2,0)+"   "+b.balancefactor(2));
       System.out.println("8     "+b.getNodeHeight(root,8,0)+" "+b.balancefactor(8));
       System.out.println("65    "+b.getNodeHeight(root,65,0)+" "+b.balancefactor(65));
       System.out.println("92    "+b.getNodeHeight(root,92,0)+" "+b.balancefactor(92));
   }
}
class Node{
   int data;
   Node left;
   Node right;  
   public Node(int data){
       this.data = data;
       left = null;
       right = null;
   }
}