Question

JAVA PROGRAM

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.

Node Height Balance Factor

2          0

65    0

92    0

8          1

89        1

85         2

3           1

5           3

Answer 1

public class BinarySearchTree {

        class TreeNode {
                public int key;
                public TreeNode p;
                public TreeNode left;
                public TreeNode right;

                public TreeNode() {
                        p = left = right = null;
                }

                public TreeNode(int k) {
                        key = k;
                        p = left = right = null;
                }
        }

        public TreeNode root;

        public BinarySearchTree() {
                root = null;
        }

        public void insert(int k) {
                TreeNode newNode = new TreeNode(k);
                
                if(root == null) {
                        root = newNode;
                } else {
                        TreeNode parent = root;
                        while(true) {
                                if(parent.key == k) {
                                        return;
                                }
                                if(parent.key > k) {
                                        if(parent.left == null) {
                                                parent.left = newNode;
                                                newNode.p = parent;
                                                return;
                                        } else {
                                                parent = parent.left;
                                        }
                                } else {
                                        if(parent.right == null) {
                                                parent.right = newNode;
                                                newNode.p = parent;
                                                return;
                                        } else {
                                                parent = parent.right;
                                        }
                                }
                        }
                }
        }
        
        public void printReport() {
                System.out.printf("%-5s%-8s%-5s\n", "Key", "Height", "Balance Factor");
                printReport(root, 1);
        }
        
        private void printReport(TreeNode start, int height) {
                if(start == null) {
                        return;
                }
                System.out.printf("%-5d%-8d%-5d\n", start.key, height, balanceFactor(start));
                printReport(start.left, height + 1);
                printReport(start.right, height + 1);
        }
        private int depth(TreeNode start) {
                if(start == null) {
                        return 0;
                }
                return 1 + Math.max(depth(start.left), depth(start.right));
        }
        private int balanceFactor(TreeNode start) {
                return depth(start.left) - depth(start.right);
        }
        

        /**
         * @param args
         */
        public static void main(String[] args) {
                int[] array = { 5, 85, 89, 3, 2, 8, 65, 92 };
                BinarySearchTree bst = new BinarySearchTree();
                for (int i = 0; i < array.length; i++)
                        bst.insert(array[i]);
                
                bst.printReport();
        }

}

**************************************************

Thanks for your question. We try our best to help you with detailed answers, But in any case, if you need any modification or have a query/issue with respect to above answer, Please ask that in the comment section. We will surely try to address your query ASAP and resolve the issue.

Please consider providing a thumbs up to this question if it helps you. by Doing that, You will help other students, who are facing similar issue.