Question

In: Computer Science

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 element, and Print the tree in "inorder" format.

Enter the following tree :

BinaryTree Test your program in case you have two identical trees and another time when you have different trees.

Java Please!

Solutions

Expert Solution

package DS;

// Class for BSTNode
class TNode
{
   // To store key value
   public int key;
   // To point to left child
   public TNode left;
   // To point to right child
   public TNode right;
  
   // Default constructor to initialize instance variables
   public TNode(int key)
   {
       this.key = key;
       left = null;
       right = null;
       key = 0;
   }// End of default constructor  
}// End of class BSTNode

// Defines class TreeNode for binary search tree
class TreeNode
{
   // Declares root node
   public TNode root;
          
   // Default constructor to initialize root
   public TreeNode()
   {
       this.root = null;
   }// End of default constructor
  
   // Method to insert key
   public void insert(int key)
   {
       // Creates a node using parameterized constructor
       TNode newNode = new TNode(key);
          
       // Checks if root is null then this node is the first node
       if(root == null)
       {
           // root is pointing to new node
           root = newNode;
           return;
       }// End of if condition
          
       // Otherwise at least one node available
      
       // Declares current node points to root
       TNode currentNode = root;
       // Declares parent node assigns null
       TNode parentNode = null;
          
       // Loops till node inserted
       while(true)
       {
           // Parent node points to current node
           parentNode = currentNode;
          
           // Checks if parameter key is less than the current node key
           if(key < currentNode.key)
           {
               // Current node points to current node left
               currentNode = currentNode.left;
              
               // Checks if current node is null
               if(currentNode == null)
               {
                   // Parent node left points to new node
                   parentNode.left = newNode;
                   return;
               }// End of inner if condition
           }// End of outer if condition
          
           // Otherwise parameter key is greater than the current node key          
           else
           {
               // Current node points to current node right
               currentNode = currentNode.right;
              
               // Checks if current node is null
               if(currentNode == null)
               {
                   // Parent node right points to new node
                   parentNode.right = newNode;
                   return;
               }// End of inner if condition
           }// End of outer if condition
       }// End of while
   }// End of method
  
   // Method to return biggest key
   int maxValue()
   {
       // Stores the root key as the maximum
       int maximum = root.key;
      
       // Loops till right child is not null
       while(root.right != null)
       {
           // Stores the maximum as the current key
           maximum = root.right.key;
           // Move to next right child
           root = root.right;
       } // End of while loop
      
       // Returns the maximum
       return maximum;
   } // End of method
  
   // Method for In Order traversal
public void inorder()
{
inorder(root);
}//End of method
  
   // Method for In Order traversal recursively
private void inorder(TNode root)
{
   // Checks if root is not null
if (root != null)
{
   // Recursively calls the method with left child
inorder(root.left);
// Displays current node value
System.out.print(root.key + " ");
// Recursively calls the method with right child
inorder(root.right);
}// End of if condition
}// End of method
  
// Method to return true if both the BST is equals
// Otherwise returns false
boolean checkEqual(TNode one, TNode two)
{
   // Checks if both the parameter node is null then return true
   if((one == null) && (two == null))
       return true;
  
   // Otherwise checks if first node is not null and second node is null
   // or first node is null and second node not null then return false
   else if((one != null && two == null)||(one == null && two != null))
       return false;
  
   // Otherwise checks if first node key is equals to second node key
   else if(one.key == two.key)
       // Recursively calls the method with left child for both
       // and right
       return checkEqual(one.left, two.left) && checkEqual(one.right, two.right);
  
   // Otherwise returns false
   else
       return false;
}// End of method
}// End of class TreeNode

// Driver class definition
public class BinaryTreeNode
{
   // main method definition
   public static void main(String []s)
   {
       // Creates TreeNode class temporary object using default constructor
       TreeNode t = new TreeNode();
      
       // Creates TreeNode class object one using default constructor
       TreeNode one = new TreeNode();
       // Calls the method to insert to tree one
       one.insert(11);
       one.insert(44);
       one.insert(22);
       one.insert(3);
       one.insert(33);
      
       // Creates TreeNode class object two using default constructor
       TreeNode two = new TreeNode();
       // Calls the method to insert to tree two
       two.insert(11);
       two.insert(44);
       two.insert(22);
       two.insert(3);
       two.insert(33);
      
       // Creates TreeNode class object three using default constructor
       TreeNode three = new TreeNode();      
       // Calls the method to insert to tree three
       three.insert(9);
       three.insert(1);
       three.insert(7);
       three.insert(90);
       three.insert(50);
      
       // Calls the method to perform in order traversal for 3 trees
       System.out.println("\n\n **************Inorder Traversal BST One **************");
       one.inorder();
       System.out.println("\n\n **************Inorder Traversal BST Two **************");
       two.inorder();
       System.out.println("\n\n **************Inorder Traversal BST Three **************");
       three.inorder();
      
      
       // Calls the method to check equality of one and two BST
       if(t.checkEqual(one.root, two.root))
           System.out.print("\n\n Both BST One and BST Two are equal.");
       else
           System.out.print("\n\n BST One and BST Two are equal.");
      
       // Calls the method to check equality of one and three BST
       if(t.checkEqual(one.root, three.root))
           System.out.print("\n\n Both BST One and BST Three are equal.");
       else
           System.out.print("\n\n BST One and BST Three are not equal.");
      
       // Calls the method to display the maximum value of each BST
       System.out.println("\n\n Maximum value in BST One: " + one.maxValue());
       System.out.println("\n Maximum value in BST Two: " + two.maxValue());
       System.out.println("\n Maximum value in BST Three: " + three.maxValue());
   }// End of main method
}// End of driver class

Sample Output:

**************Inorder Traversal BST One **************
3 11 22 33 44

**************Inorder Traversal BST Two **************
3 11 22 33 44

**************Inorder Traversal BST Three **************
1 7 9 50 90

Both BST One and BST Two are equal.

BST One and BST Three are not equal.

Maximum value in BST One: 44

Maximum value in BST Two: 44

Maximum value in BST Three: 90


Related Solutions

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++
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]
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
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
​Define a tree. Distinguish between a tree and a binary tree. Distinguish between a binary tree and a binary search tree.
Define a tree. Distinguish between a tree and a binary tree. Distinguish between a binary tree and a binary search tree.
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.
Question 2: Create a method (sortTraversal) for a Binary Search Tree that prints out the Binary...
Question 2: Create a method (sortTraversal) for a Binary Search Tree that prints out the Binary Search Tree in ascending or deceasing order. The order type is an input to the method and can be "ascending" or "descending". The ascending input would return the node values of the tree beginning with the smallest and ending with the largest, descending returns the opposite. Discuss method's Big-O notation. Add proper and consistent documentation to identify code sections or lines to clearly identify...
PYTHON CODING Create a method (sortTraversal) for a Binary Search Tree that prints out the Binary...
PYTHON CODING Create a method (sortTraversal) for a Binary Search Tree that prints out the Binary Search Tree in ascending or deceasing order. The order type is an input to the method and can be "ascending" or "descending". The ascending input would return the node values of the tree beginning with the smallest and ending with the largest, descending returns the opposite. Discuss method's Big-O notation. Add proper and consistent documentation to identify code sections or lines to clearly identify...
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...
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...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT