Question

Create a Binary Search Tree with the following elements in the order mentioned below:

5, 85, 89, 3, 2, 8, 65, 92

Print the Pre-order of this tree

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.

Typed JAVA Program!

Java language

Answer 1

The Code for the following question is :

import java.util.Scanner;

//Creating class for the node
class Node{
       int data;
       Node left,right;
      
      Node(int data){
         this.data = data;
         left = right = null;
     }
}

public class BstBalanceFactor {

    Node root;

    // Constructor
    BstBalanceFactor() {
        root = null;
    }

    // This method mainly calls insertRec()
    void insert(int key) {
        root = insertRec(root, key);
    }

    /* A recursive function to insert a new key in BST */
    Node insertRec(Node root, int key) {

        /* If the tree is empty, return a new node */
        if (root == null) {
            root = new Node(key);
            return root;
        }

        /* Otherwise, recur down the tree */
        if (key < root.data)
            root.left = insertRec(root.left, key);
        else if (key > root.data)
            root.right = insertRec(root.right, key);

        /* return the (unchanged) node pointer */
        return root;
    }

    // This method mainly calls PreorderRec()
    void Preorder()  {
        PreorderRec(root);
    }
    void PreorderRec(Node node)
    {
        if (node == null)
            return;

        /* first print data of node */
        System.out.print(node.data + " ");


        PreorderRec(node.left);


        PreorderRec(node.right);
    }


    public int getHeight(Node n){
        if(n == null) {
            return -1;
        }

        return Math.max(getHeight(n.left), getHeight(n.right))+1;
    }
    // Find the BalanceFactor of a Node
    public int BalanceFactor( Node node){
         int balanceFactor = 0;
         if (node == null)
            return 0;

        if (node.left == null && node.right == null)
            return 1;

        int heightL = BalanceFactor(node.left);
        int heightR = BalanceFactor(node.right);


        balanceFactor = heightL - heightR;
        return balanceFactor;

    }

    //Printing the output
    public  void print(){
        printRec(root);
    }

    //Recursive call to print()
    public  void  printRec(Node node){

        if(node != null) {
            System.out.println(node.data + " " + getHeight(node) + " " + BalanceFactor(node));

            printRec(node.left);
            printRec(node.right);
        }

    }
    public static void main(String args[]){
        BstBalanceFactor tree = new BstBalanceFactor();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int array[] = new int[n];
        for (int i = 0; i <n ; i++) {
            array[i] = sc.nextInt();
        }

        for (int i = 0; i <n ; i++) {
            tree.insert(array[i]);
            //tree.print();
        }

        tree.Preorder();
        System.out.println();
        System.out.println(" Node " + "Height " + "Balance Factor " );
        tree.print();


    }
}

/*****************************************************************************************************************************************/

The screenshot of the output is attached here

"C:Program Files\Java dk1.8.0 191\bin Gava.exe". 5 85 89 3 2 8 65 92 5 3 2 85 8 65 89 92 Node Height Balance Factor 5 3 1 3 1 1 201 85 20 8 1-1 65 0 1 89 1 -1 92 0 1 Process finished with exit code 0