Implementing Binary Search Tree Insert operation in Java

Question

I have a TreeNode class that represents node of the binary tree.

public class TreeNode {

private static Object key=null;
private static Object value=null;
private TreeNode parent;
private TreeNode left=null;
private TreeNode right=null;    
/**
 * @return the value
 */
public static Object getValue() {
    return value;
}

/**
 * @param aValue the value to set
 */
public static void setValue(Object aValue) {
    value = aValue;
}


public TreeNode()
{
    this(key,value);
}
public TreeNode(Object key,Object value)
{
    this.key = key;
    this.value = value;
}
/**
 * @return the key
 */
public Object getKey() {
    return key;
}

/**
 * @param key the key to set
 */
public void setKey(Object key) {
    this.key = key;
}

/**
 * @return the parent
 */
public TreeNode getParent() {
    return parent;
}

/**
 * @param parent the parent to set
 */
public void setParent(TreeNode parent) {
    this.parent = parent;
}

/**
 * @return the left
 */
public TreeNode getLeftChild() {
    return left;
}

/**
 * @param left the left to set
 */
public void setLeftChild(TreeNode left) {
    this.left = left;
}

/**
 * @return the right
 */
public TreeNode getRightChild() {
    return right;
}

/**
 * @param right the right to set
 */
public void setRightChild(TreeNode right) {
    this.right = right;
}

}

I have a BinarySearchTree class

public class BinarySearchTree implements DataStructures.interfaces.BinarySearchTree {
private int size=0;
private TreeNode root = new TreeNode();

@Override
public void insert(Object key, Object value)
{
    insertOperation(key,value,root);
}

private void insertOperation(Object element, Object value, TreeNode node)
{

    if(node.getKey() == null) {
        node.setKey(element);
        node.setValue(value);            
    }
    else
    {
        if((int) node.getKey() > (int) element)
        {
            if(node.getLeftChild() != null)
                insertOperation(element,value,node.getLeftChild());
            else
            {
                TreeNode child = new TreeNode(element, value);
                child.setKey(element);
                child.setValue(value);
                child.setParent(node);
                node.setLeftChild(child);

                size++;
            }
        }
        else if((int) node.getKey() <= (int) element)
        {
            if(node.getRightChild() != null)
                insertOperation(element,value,node.getRightChild());
            else
            {
                TreeNode child = new TreeNode(element, value);
                child.setKey(element);
                child.setValue(value);
                child.setParent(node);
                node.setRightChild(child);

                size++;
            }
        }
    }

  }
  ///more methods
}

The problem is that when I create a child node and set the parent child link. The value of parent node (the node object that I passed) also gets updated and refers to child object.

That is not my intention.

I want to create a chain of treenode objects that can be accessed through the "root" treenode object.

But this is not happening and I do not understand what I am doing wrong.

I know that the problem lies in the logic of this code snippet (not just for inserting on left side but both for inserting left child and right), but I do not understand what exactly.

           if(node.getLeftChild() != null)
                insertOperation(element,value,node.getLeftChild());
            else
            {
                TreeNode child = new TreeNode(element, value);
                child.setKey(element);
                child.setValue(value);
                child.setParent(node);
                node.setLeftChild(child);

                size++;
            }

All I am telling java to do is if the node in question does not have a left child then create a left child node and set the current node's left side object to the child object.

if the node in question does have a left child then inspect that child and see if the new node should be inserted in left or right by calling the same function for the child of the node in question ... I don't understand why node's (the TreeNode object passed) key gets updated, when i set child's key value.

Answer 1

Why are your key and value static Objects? This means all TreeNodes would share the same key/value. Remove the static keyword and it should work fine.

Answer 2

I don't quite get what you mean by

The problem is that when I create a child node and set the parent child link. The value of parent node (the node object that I passed) also gets updated and refers to child object.

but I did notice one thing that will result an error:

    else if((int) node.getKey() <= (int) element)

When node.getKey() == element, it means the bst already has a node with "element" as the key, which should be another special case. Instead you're still traversing through its right child.

Also, it would be nice if you can elaborate your error more clearly...