Question

In: Computer Science

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

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

Solutions

Expert Solution

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.


Related Solutions

Create a Binary Search Tree with the following elements in the order mentioned below: 5, 85,...
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...
Binary Tree Create a binary search tree using the given numbers in the order they’re presented....
Binary Tree Create a binary search tree using the given numbers in the order they’re presented. State if the resulting tree is FULL and/or BALANCED. 37, 20, 18, 56, 40, 42, 12, 5, 6, 77, 20, 54
C++ Instantiate a binary search tree object and create such tree using elements of the sequence...
C++ Instantiate a binary search tree object and create such tree using elements of the sequence 8,3,10, 1,6,9, 14, 4,7, 13 with 8 as root of the tree. Find maximum and minimum elements of the tree, successor(10) and predecessor(13), print the inorder, postorder and preorder traversal of the tree.
Create a Binary Search Tree for the following data and do In-order, Preorder and Post-order traversal...
Create a Binary Search Tree for the following data and do In-order, Preorder and Post-order traversal of the tree. 50, 60, 25, 40, 30, 70, 35, 10, 55, 65, 5 Write an algorithm to delete a node in Singly Linked List                            [12 Write an algorithm of Binary Search                                                              [10] Write a program in ‘C’ to generate Fibonacci series using recursion            [8]
Write a JAVA program to modify the insert and remove of a binary search tree to...
Write a JAVA program to modify the insert and remove of a binary search tree to become an AVL tree.
Problem 1: Write a Java program for traversing a Binary Search Tree in following ways: (use...
Problem 1: Write a Java program for traversing a Binary Search Tree in following ways: (use any data structure, library functions) ---------- 20 points i) Depth First Traversal: Inorder, LVR ii) Depth First Traversal: Inorder, RVL iii) Depth First Traversal: Preorder, VLR iv) Depth First Traversal: Preorder, VRL v) Depth First Traversal: Postorder, LRV vi) Depth First Traversal: Postorder, RLV No choice menu required. Sample Input (taken from keyboard, single space separated nodes as found in a complete BFS: top-down,...
Create a new project to build a Binary search tree, and do the following: Create a...
Create a new project to build a Binary search tree, and do the following: Create a TreeNode class, Add the methods "Insert" to insert new nodes to the tree. Add the method "inorder". Make the method to return a list of the node elements in inorder. Implement the equals method in the BST. Two BST are equal if they contain the same elements. In the main insert the elements of the tree, call the max method and print the max...
Write the binary tree representation for the Binary Search for also 17 elements and give the...
Write the binary tree representation for the Binary Search for also 17 elements and give the worst-case
Prerequisite Knowledge Understand binary search tree structure Understand binary search tree operations Understand binary search tree...
Prerequisite Knowledge Understand binary search tree structure Understand binary search tree operations Understand binary search tree worst case and best case time. Learning Outcomes Describe AVL tree structure Trace and implement AVL tree operations Explain and prove AVL tree performance
Build a binary search tree with the following words. Insert them in an order so that...
Build a binary search tree with the following words. Insert them in an order so that the tree has as small a depth as possible. (Consider the insertion order of the words) Print the tree after,also, any, back, because, come, day, even, first, give, how, its, look, most, new, now, only, other, our, over, than, then, these, think, two, us, use, want, way, well, work. C++
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT