Array implementation of unbalanced binary search tree

I'm preparing for an interview.

Always a good move.

I tried implementing binary search tree in C++. I used array

An interesting choice (it can be done). But usually an array is reserved for implementing a heap (in terms of tree structures). This is because it is always balanced with no holes in the middle. A binary search tree does not necessarily need to be balanced (its preferable but not required) and may have gaps so an array does not lend itself well to representing the leaf nodes.

Is linked list a better data structure to implement BST?

Not really. You may as well implement a tree structure directly.

Also please let me know if the code has bad coding practice like memory leak, bad data structure, poor algorithm, unnecessarily using a lot of memory, etc.

You bet yea :-)

Having a quick look at the code. The size worries me. A BST is a simple structure and should not take this much effort.

NULL is not a magic value

This is showing a lack of understanding of the type system (are you coming from a Java background?).

        arrayOfNodes[i].key = NULL;
        arrayOfNodes[i].value = NULL;

Both of these are integers. There is no such concept as a NULL value. What is happening here is that NULL is being converted to an integer (zero) and assigned to the values. You can not tell the difference between a NULL and a zero so unless you want to reserve the special key zero this has no meaning.

For the rest of the code I will assume that a zero Key means the value is unused. But note magic numbers like this are discouraged.

Interface design

bool insert(node n, int i=0)

Note sure I understand what the i parameter is for (do I need to read the documents). Also why require the user to create a node object to insert. You could just express this as part of the interface.

bool insert(int key, int value)  // ?? This is what I would have expected.

Should use references

    node current = arrayOfNodes[i];

I see you are using the i to index into your array. Then its a VERY bad idea to put it on the public interface to your class. You should be working out where in the array to put the object not asking the user where the object goes (the internal state of you object is being messed with by external users thus you are breaking encapsulation).

    node current = arrayOfNodes[i];

This line is not doing what you thinkg. Here you are making a copy of the object in your tree(array). Any changes to current are not reflected inside the tree(array). If you want to manipulate the tree your need a reference (unlike Java/C#) you have to explicitly declare references otherwise they are local objects.

    node&   current = arrayOfNodes[i]; // Notice the & at the start.

Quick Primer on the different types of object.

    node    data1;   // creates a local node object.
                     // Its constructor is called before we go further.
                     // The destructor will be called when it goes
                     // out of scope (look for the closest '}' usually).

    node&   data2 = data1;   // create a reference.
                     // data2 is just another name for data1.
                     // manipulate data2 and data1 is affected.

    node*   data3 = &data1;  // data3 is a pointer
                     // It points at the address of an object. You
                     // can manipulate the object being pointed
                     // at via the pointer.
                     //
                     // This is closer to your Java/C# types as this
                     // value can be NULL (meaning points at nothing)
                     // You can also hold pointers to dynamically
                     // allocated data (unlike Java/C# these must be
                     // manually deletes (as such we don't use them
                     // much and prefer to use smart pointers for
                     // memory management).

Don't put everthing on one line

    if(current.key == NULL) {arrayOfNodes[i].key = n.key; arrayOfNodes[i].value = n.value;}

This makes code hard to read (and thus maintain). Also not everybody will read your code on a wide display.

    if(current.key == NULL) {
        arrayOfNodes[i].key   = n.key;
        arrayOfNodes[i].value = n.value;
    }

OK I also see where you are going with your interface now.

    else if (n.key < current.key) return insert(n, 2*i+1);
    else if (n.key > current.key) return insert(n, 2*i+2);

To do this properly you should have had a public interface that does not allow the user to specify an i parameter. All this does is delegate to a private method and default the value to 0.

public:
    bool insert(node n)  {return insert(n, 0);}
private:
    bool insert(node n, int i) // External user can not call thi
    {                          // Thus can not break your internal
         // DO work.           // structure by specifying a bad `i`
    }

Check Invariants and return quickly.

If you check you invarants quickly at the top of the function and return. Then you don't need to indent the rest of the code. It is obvious that the remaining code is only being used if the invariants hold.

    int i = findPos(key, n); //position of the node to be deleted
    if(i == -1 || arrayOfNodes[i].key == NULL) return false;
    else
    {
         ... The main body of work
    }

I would have written this as:

    int i = findPos(key, n);
    if(i == -1 || arrayOfNodes[i].key == NULL) {
        return false;
    }

    // We have a valid item to delete so remove it from the tree and
    // update all children.
    ....

Don't write useless comments

    int i = findPos(key, n); //position of the node to be deleted

I can read the code which because of good function naming actually tells me more than the comment. Writing bad/useless comments is actually much worse than writing no comments as you now have to maintain the comments and make sure they are the same as the code.

When writing comments do not explain what a line of code does. The code is usually better than the comment. Use your comments to explain WHY you are doing something or explain an algorithm. Don't explain the code (the code explains its self).

Simplify the delete.

You have deleted a node. Because of the way you hold the tree (an array) you must fill that node. The invariant you must maintain is that all nodes on the left are smaller and all nodes on the right are larger.

A simple trick is: look at the left tree. Then find the largest value in that subtree. It will be bigger than all the other values on the left yet smaller than all the values on the right. You can then use it as the node to replace the current node.

If the left tree is empty. You can use the same trick on the right (just pick the smallest node on the right).

bool deletenode(int key)
{
    int find = findPos(key);
    if (find == arrayOfNodes[find].key == 0) {
        return false;
    }

    deleteFromLoction(i);
    return true;
}
void deleteFromLoction(int find)
{
    int replacement = findLargest(find*2+1);
    if (replacement == -1 || arrayOfNodes[replacement].key == 0) {
        replacement = findSmallest(find*2+2);
    }

    arrayOfNodes[find].key = 0
    if (replacement != -1 && arrayOfNodes[replacement].key != 0) {
        std::swap(arrayOfNodes[replacement], arrayOfNodes[find]);
        deleteFromLoction(replacement);
    }
}

Answer to some questions:

1) What you mean by implement a tree structure directly? Can you provide me with a sample code?

class Node
{
    public:
        int    key;
        int    value;
        Node*  left;        // point to the next node
        Node*  right;       // in the node itself.
};

2) I understand that assigning NULL won't differentiate it from 0. But how to differentiate between initiated and uninitiated nodes?

You can't do it automatically.

I can think of two techniques quickly off the top of my head:

• Add a member to your node to mark it as nused.
• Change your array to an array of pointers.
  • Unused values are NULL otherwise the point at a real node.
  • You will need a technique to handle the node objects.

3) the simpler delete logic you suggested is great. But it has to be recursively done right? i.e the replaced node has to be deleted next.

Yes. Sorry for the initial mistake. You are correct. I have now fixed it.