Question

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!

Answer 1

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