Implementing an insert function onto array implementation of Binary Search Tree

Question

I am attempting to use the functionality of Binary Search Trees without actually create Node objects and giving them left/right children and instead using the basic idea of a Binary Search Tree within three parallel arrays: left, data, and right. At a particular index in these arrays, left holds the index to data where the current data's left child lives, while right holds the index to data where the current data's right child lives. This table gives a better example of what I am talking about:

The -1 values represent where a node does not have a left or right child. Before any nodes are inserted, all of the arrays hold the value 0, and every time a node is inserted, its left and right children index values are set to -1 (indicating that what we just inserted is a leaf). What I'm struggling to figure out is to how to do this recursively without accidentally accessing an index of -1. My current attempt seen below is running into this issue:

public void insert(int d) {
//PRE: the tree is not full
//if d is not in the tree insert d otherwise the tree does not change
    if(root == -1) {
        root = d;
    }
    insert(d, 0);
}

private void insert(int d, int index) {
    if(data[index] == d) {
        return;
    }
    if(data[index] == 0) {
        data[index] = d;
        right[index] = -1;
        left[index] = -1;
    }
    if(data[index] > d) {
        if(left[index] == 0) {
            data[index] = d;
            right[index] = -1;
            left[index] = -1;
        } else {
            insert(d, left[index]);
        }
    }
    if(data[index] < d) {
        if(right[index] == 0) {
            data[index] = d;
            right[index] = -1;
            left[index] = -1;
        } else {
            insert(d, right[index]);
        }
    }
    return;
}

I'm curious for ideas as to how I can prevent from accessing an array with index value -1, while still being able to indicate that a node does not have a child to a particular side.

I understand the concept that every time I'm inserting a node, I'm inserting a leaf, so when a node is placed at a particular index, its left and right can automatically be set to -1, but my current recursive calls end up passing in -1 at one point or another. Even if I change this value to 0, or something else, that doesn't necessarily help me make any progress in my recursion.

Answer 1

Some remarks on your code:

• The root variable should not be assigned d, but the index where d will be stored, only then does it make sense that an empty tree is encoded with root equal to -1 (realise that d could be -1).

• Your code has no logic to determine at which index to store a new node. This is really your question. A simple solution is to maintain a size variable. This is then the index at which the next node will be stored, after which the size member should be incremented.

• There is then never a reason to think of 0 as some special indicator, and your code should only check for -1 references, not 0.

• You have some code repetition which you can avoid by creating a method that will "create" a node: it will use size for its index, and will take a value as argument.

Here is the suggested code:

class BinaryTree {
    public static final int MAXSIZE = 100;
    int left[] = new int[BinaryTree.MAXSIZE]; 
    int right[] = new int[BinaryTree.MAXSIZE]; 
    int data[] = new int[BinaryTree.MAXSIZE]; 
    int root = -1;
    int size = 0;

    private int createNode(int value) {
        data[size] = value;
        left[size] = -1;
        right[size] = -1;
        return size++;
    }

    public void insert(int value) {
        if (root == -1) {
            root = createNode(value);
        } else {
            insert(value, 0);
        }
    }

    private void insert(int value, int index) {
        if (data[index] == value) {
            return;
        }
        if (data[index] > value) {
            if (left[index] == -1) {
                left[index] = createNode(value);
            } else {
                insert(value, left[index]);
            }
        } else {
            if (right[index] == -1) {
                right[index] = createNode(value);
            } else {
                insert(value, right[index]);
            }
        }
        return;
    }
}

This code can be further extended with:

• verification that the tree has reached a maximum size,
• node deletion
• "memory management" for reusing the indexes of deleted nodes (by maintaining a "free list")
• self-balancing (like AVL or red-black tree)

Doing the "memory management" (array slot management) yourself is really going to mimic the powerful heap memory management that Java offers out of the box when using class instances. For that reason I would advise to implement a tree the OOP way.