Array implementation of unbalanced binary search tree

I'm preparing for an interview. I tried implementing binary search tree in C++. I used array but it seems to be complicated to restructure the array while deleting nodes. Is linked list a better data structure to implement BST? 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.

```
// bst.cpp : Defines the entry point for the console application.
// array implemenation of unbalanced bst without duplicates

#include "stdafx.h" //by default
#include
#include

using namespace std;

class node
{
public:
int key;
int value;
};

class tree
{
private:
node arrayOfNodes[100];

public:
tree()
{
for(int i=0; i current.key) return insert(n, 2*i+2);
}

void print()
{
int i = 0;
while(i 1) / While x is even and > 1 /
x /= 2;
return (x == 1);
}

int findPosOfMin(int i=0)
{
if(2*i+1 > 100) return i;
else if(arrayOfNodes[2*i+1].key == NULL) return i;
else return findPosOfMin(2*i+1);
}

int findPos(int key, int i=0)
{
node current = arrayOfNodes[i];
if(i > 100 || current.key == NULL) return -1;
if(current.key == key) return i;
else if (key current.key) return findPos(key, 2*i+2);
}

node find(int key, int i=0)
{
node current = arrayOfNodes[i];
if(i > 100 || current.key == NULL) return current;
if(current.key == key) return current;
else if (key current.key) return find(key, 2*i+2);
}
};

int _tmain(int argc, _TCHAR* argv[]) // by default
{
char c = 'Y';
tree t;
while(c!='N')
{
cout>c;
if(c == 'I')
{
node n; //memory leak?
cout>n.key;
cout>n.value;
t.insert(n);
}
else if(c == 'F')
{
int key;
cout>key;
node n = t.find(key);

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+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

StackExchange Code Review Q#84704, answer score: 4