Question

Binary Search Tree Code in Java

Write a program that prompts user to enter however many numbers they want to add to the binary search tree. Then have the user input numbers until the tree contains that many elements. If the user enters a number that already exists in the tree, then a message should be displayed "Number is already in the tree". Once all elements are added to the tree print its contents in sorted order.

Assume all user input is valid.

Answer 1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

//BinarySearchTree.java

import java.util.Scanner;

public class BinarySearchTree {

      // attributes for storing the root node and size

      private Node root;

      private int size;

      // constructor

      public BinarySearchTree() {

            root = null;

            size = 0;

      }

      // method to add a number to the tree, returns true if added successfully,

      // false if number already exists.

      public boolean add(int data) {

            // if root is null, adding as root node, otherwise calling recursive

            // helper method to add

            if (root == null) {

                  root = new Node(data);

                  size++;

                  return true;

            } else {

                  return add(data, root);

            }

      }

      // recursive helper method to add a number, after finding proper position

      private boolean add(int data, Node node) {

            // if node's data is same as data, returning false (duplicate)

            if (node.data == data) {

                  return false;

            }

            // if data is smaller than node's data, moving to left subtree,

            // otherwise moving to right subtree

            else if (data < node.data) {

                  // if left subtree is null, adding as left node

                  if (node.left == null) {

                        node.left = new Node(data);

                        size++;

                        return true;

                  } else {

                        // otherwise moving to left node recursively and adding at

                        // proper position

                        return add(data, node.left);

                  }

            } else {

                  // if right subtree is null, adding as right node

                  if (node.right == null) {

                        node.right = new Node(data);

                        size++;

                        return true;

                  } else {

                        // otherwise moving to right node recursively and adding at

                        // proper position

                        return add(data, node.right);

                  }

            }

      }

      // method to print elements in order (sorted)

      public void inorderTraversal() {

            // calling recursive helper method, passing root

            inorderTraversal(root);

      }

      // recursive helper method to print elements in order

      private void inorderTraversal(Node node) {

            // if node is null, exiting from method (base case)

            if (node == null) {

                  return;

            }

            // performing in order traversal on left tree

            inorderTraversal(node.left);

            // printing / visiting current node's data

            System.out.print(node.data + " ");

            // performing in order traversal on right tree

            inorderTraversal(node.right);

      }

      // returns the size

      public int getSize() {

            return size;

      }

      /**

      * main method to interact with the user

      */

      public static void main(String[] args) {

            Scanner scanner = new Scanner(System.in);

            // creating a binary search tree

            BinarySearchTree tree = new BinarySearchTree();

            System.out.print("How many numbers do you want to add? ");

            // reading tree size

            int n = scanner.nextInt();

            // loops until tree's size becomes n

            while (tree.getSize() < n) {

                  // asking for a number, reading it, adding to tree

                  System.out.print("Enter number #" + (tree.getSize() + 1) + ": ");

                  int num = scanner.nextInt();

                  if (!tree.add(num)) {

                        // if addition returned false, displaying error

                        System.out.println("Number is already in the tree");

                  }

            }

            // displaying elements in sorted order

            System.out.println("Tree in sorted order: ");

            tree.inorderTraversal();

      }

}

// simple Node class to represent a single node. should be placed in same file

class Node {

      int data;

      Node left, right;

      public Node(int data) {

            this.data = data;

      }

}

/*OUTPUT*/

How many numbers do you want to add? 10

Enter number #1: 23

Enter number #2: 19

Enter number #3: 0

Enter number #4: 45

Enter number #5: 33

Enter number #6: 12

Enter number #7: 23

Number is already in the tree

Enter number #7: 0

Number is already in the tree

Enter number #7: 70

Enter number #8: 2

Enter number #9: -2

Enter number #10: 4

Tree in sorted order:

-2 0 2 4 12 19 23 33 45 70