Implementing the add method for a Binary Search Tree

Question

My partner and I are implementing a Binary Search Tree for a Data Structures & Algorithms course. We are encountering issues with our add method. This code is shown below:

public class BinarySearchTree<Type extends Comparable<? super Type>> implements SortedSet<Type>
{


BinaryNode<Type> thisRoot;

/**
 * Constructor for this BinarySearchTree
 */
public BinarySearchTree()
{
    thisRoot = null;
}

/**
 * Adds the specified item to this BinarySearchTree, if it is
 * not already contained in this BinarySearchTree.
 * 
 * @param Type item
 * 
 * @return boolean
 */
public boolean add(Type item) {

    // If the specified item is null, throw an exception.
    if(item == null)
        throw new NullPointerException();

    // Otherwise, add the item.
    return addItem(item, thisRoot);

}

private boolean addItem(Type item, BinaryNode<Type> thisRoot)
{
    // Base case - check if thisRoot is null.  If it is null,
    // we have reached the base case where the item is not contained
    // in this BinarySearchTree.  Insert the item.
    if(thisRoot == null)
    {   
        thisRoot = new BinaryNode<Type>(item);
        return true;
    }

    // Reduction step - recursively call the helper method until the
    // specified item is found or added.

    // If the item is less than the data in thisNode, then go to 
    // the left in this BinarySearchTree.
    if(item.compareTo(thisRoot.getData()) < 0)
        return addItem(item, thisRoot.getLeft());

    // If the item is greater than the data in thisNode, then go
    // to the right in this BinarySearchTree.
    else if (item.compareTo(thisRoot.getData()) > 0)
        return addItem(item, thisRoot.getRight());
    else
        // Item is already contained in this BinarySearchTree.
        return false;

}

In our test case, we aren't getting the outcome that we expected. We initially created an empty BinarySearchTree and called on the add method. From here we passed an Integer object (10) to the method. After doing this, the recursive addItem method should have been invoked. thisRoot should currently refer to null (as we created an empty BinarySearchTree) and thus thisRoot should now refer to the new BinaryNode object. However, 10 is not contained in the BST after the method call. thisRoot still points to null. If anyone has any suggestions or insight as to why this might be, we would greatly appreciate it.

Fred Foo · Accepted Answer · 2013-06-22 18:59:53Z

2

Inside the addItem method, thisRoot is just a local variable (bound to the second argument of the method). Resetting it doesn't change anything except inside the method. You have to assign the new BinaryNode<Type>(item) that you construct to either the left or right pointer of an existing node.

(If I'm being vague, that's because I don't want to give the answer away.)

answered Jun 22, 2013 at 18:59

Fred Foo

365k80 gold badges765 silver badges852 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Jonathan Over a year ago

If you pass a reference variable as a parameter and you change that reference within the method in which it was passed, then you "are" changing the reference of the reference variable. I must be misunderstanding simple concepts from my basic programming class.

Fred Foo Over a year ago

@JonathanWhitaker: you're reassigning the reference to point to another, newly constructed object. You're not changing the object it initially references (obviously, since an attempt to do so would give a null pointer exception).

Jonathan Over a year ago

I was forgetting that there was nothing being returned and thus the reference was not changing. Thanks for the help larsmans, we appreciate it.

Roast Biter · Accepted Answer · 2019-03-28 18:53:13Z

this is a relatively easier way

also if you see any data type not declared, consider it added somewhere in the complete code.

   public void addNode (int key, String name) {

    // Create a new Node and initialize it

    Node newNode = new Node(key, name);

    if (root == null) {

        root = newNode;

    } else {

       Node focusNode = root;
        Node parent;

        while (true) {



            parent = focusNode;

            // Check if the new node should go on
            // the left side of the parent node

            if (key < focusNode.key) {

                // Switch focus to the left child

                focusNode = focusNode.leftChild;


                if (focusNode == null) {


                    parent.leftChild = newNode;
                    return; 

                }

            } else {  the right

                focusNode = focusNode.rightChild;



                if (focusNode == null) {



                    parent.rightChild = newNode;
                    return;

Collectives™ on Stack Overflow

Implementing the add method for a Binary Search Tree

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related