Argthtjtr

I am trying to write a recursive method to add a node to a binary search tree (that does not allow duplicates). For some reason, the method only works when the tree is empty, otherwise it prints out "Duplicate" (even if it is not a duplicate). I am new to programming and would appreciate help and tips to fix this. Thank you.

//add new node to the tree

public void add(int data) {

    Node<Integer> newNode = new Node<>(data); //create new node with the data



    //if the tree is empty, the newNode becomes the root

    if (size() == 0) {

        root = newNode;

        return;

    }

    //otherwise, check if node should be placed to right or left 

    add(data, root);

}

private void add(int data, Node<Integer> node) {

    //base case - found an empty position

    if (node == null) {

        node = new Node<Integer>(data);

    }

    if (data < node.data) {

        add(data, node.left);

    }

    else if (data > node.data) {

        add(data, node.right);

    }

    else if (data == node.data) {

        System.out.println("Duplicate. This value cannot be added to the tree.");

    }

}

When your tree is empty, the node is added properly to it. The first add(int data) function is fine.

The problem exists with the second add(int data, Node<Integer> node) function. In case if the tree already has an element, this method is called. If the node passed is either greater or lesser than the value passed then the function is called again with either the left or right child of the current node. This value might be (will eventually be) null. That leads to creation of a node in the base case of your method which leads to the satisfaction of this data == node.data condition as the node was indeed created with the data value. Hence you get the error message.

In order to fix this, the second function can be altered as below :

private void add(int data, Node<Integer> node) {

    if (data < node.data) {

        if (node.left != null) {

            add(data, node.left);

        } else {

            node.left = new Node<>(data);

        }

    }

    else if (data > node.data) {

        if (node.right != null) {

            add(data, node.right);

        } else {

            node.right = new Node<>(data);

        }

        add(data, node.right);

    }

    else if (data == node.data) {

        System.out.println("Duplicate. This value cannot be added to the tree.");

    }

}

See that the base case has been removed. If ever encountered the base case does not provide us with a reference to any tree node. Hence addition of data to the tree is impossible (the node argument must never be null).

Also, the code adds data as a child to node if the child is null. This guarantees that the method is not recursively with a null node argument and adds data to its rightful place more importantly.

At the end of the recursion you are not returning the actual root of the BST. "root" object that you have it is pointing to the last inserted node. So every time you are trying to insert the same value it will be inserted after the last inserted node which have the same value. Here is my implementation:

class BinarySearchTree { 





    class Node { 

        int key; 

        Node left, right; 



        public Node(int item) { 

            key = item; 

            left = right = null; 

        } 

    } 





    Node root; 



    BinarySearchTree() {  

        root = null;  

    } 





    void add(int data) { 

       root = add(root, data); 

    } 



    Node add(Node root, int data) { 





        if (root == null) { 

            root = new Node(data); 

            return root; 

        } 



        if (data < root.key) 

            root.left = add(root.left, data); 

        else if (data > root.key) 

            root.right = add(root.right, data); 

        else if( data==root.key) {

                System.out.println("Duplicate. This value cannot be added to the tree.");

        }

        return root; 

    } 





    void inorder()  { 

       inorderRec(root); 

    } 





    void inorderRec(Node root) { 

        if (root != null) { 

            inorderRec(root.left); 

            System.out.println(root.key); 

            inorderRec(root.right); 

        } 

    } 

    public static void main(String args) { 

        BinarySearchTree tree = new BinarySearchTree(); 





        tree.add(50); 

        tree.add(30); 

        tree.add(20); 

        tree.add(20);

     // print inorder traversal of the BST 

        System.out.println("Inorder traversal");

        tree.inorder(); 



        tree.add(40); 

        tree.add(40);

        tree.add(70); 

        tree.add(60); 

        tree.add(80); 

        System.out.println("Inorder traversal");

        // print inorder traversal of the BST 

        tree.inorder(); 

    } 

}