15,569,644 members
Articles / Programming Languages / C++
Article
Posted 17 Jun 2013

100.4K views
16 bookmarked

# Creating a Binary Search Tree (BST) using C++ Standard Template Library (STL) Vector

Rate me:
BST Data Structure using vector and deque

## Introduction

Whenever we create trees, we need to be careful about memory allocations and de-allocation. Just out of a requirement, I thought of trying C++ STL (vectors and deques) to create a small BST. This article is the obvious consequence of that thought.

## Background

BSTs are one of the most widely used data structures. C is the preferred language, however with the advent of C++ especially with C++11, it seems to be interesting to use C++. However, nothing related to C++11 is used in this article and can be used by C++98 compilers.

## Using the Code

To create a BST, we need a BST data structure. Traditional BST data structures contain pointer to left and right sub-tree. Since I’ll be using vector and not pointers, I'll use vector indexes as pointer to left and right sub-tree.

C++
struct bst
{
unsigned int data;
int leftIdx;
int rightIdx;
};

Now, I’ll write various functions used in creating the BST and its child nodes. The first function will be used to create a BST. It will initialize the data structure with incoming data and reset the left and right index with -1 (similar to making the pointers NULL).

C++
{
struct bst b1 = { aData, -1, -1 };
v1.push_back(b1);
}

The functions below will set the left and right child of a node. While setting, it assigns the correct index of left and right child on to the root node:

C++
void setleft(vector <struct>&v1, int currIndex, int aData)
{
unsigned int leftIndex = v1.size();
v1[currIndex].leftIdx = leftIndex;
struct bst b1 = { aData, -1, -1 };
v1.push_back(b1);
}

void setright(vector<struct> &v1, int currIndex, int aData)
{
unsigned int rightIndex = v1.size();
v1[currIndex].rightIdx = rightIndex;
struct bst b1 = { aData, -1, -1 };
v1.push_back(b1);
}

The function below will be used to insert the data into the BST. Simple traversal to all the nodes till we find the appropriate place to insert the elements and call left and right functions defined above.

C++
void Insert(vector<struct bst> &v1, int aData)
{
if(v1.size() == 0)
{
cout<<"Note is not made yet. MakeNode first..."<<endl;
return;
}
unsigned int currentIdx = 0;
while ( currentIdx < v1.size() )
{
{
if( v1[currentIdx].leftIdx == -1)
{
break;
}
else
currentIdx = v1[currentIdx].leftIdx;
}
else
{
if(v1[currentIdx].rightIdx == -1)
{
break;
}
else
currentIdx = v1[currentIdx].rightIdx;
}
}
}

The code below will be used for traversing the BST in in-order, pre-order, and post-order. The index is used as a starting point.

C++
void InTrav(vector <struct bst> &v1, unsigned int Idx)
{
if(v1[Idx].leftIdx != -1)
InTrav(v1,v1[Idx].leftIdx );
cout<<v1[Idx].data<<endl;
if( v1[Idx].rightIdx != -1)
InTrav(v1, v1[Idx].rightIdx);
}

void PreTrav(vector <struct bst> &v1, unsigned int Idx)
{
cout<<v1[Idx].data<<endl;
if(v1[Idx].leftIdx != -1)
PreTrav(v1,v1[Idx].leftIdx );
if( v1[Idx].rightIdx != -1)
PreTrav(v1, v1[Idx].rightIdx);
}
void PostTrav(vector <struct bst> &v1, unsigned int Idx)
{
if(v1[Idx].leftIdx != -1)
PostTrav(v1,v1[Idx].leftIdx );
if( v1[Idx].rightIdx != -1)
PostTrav(v1, v1[Idx].rightIdx);
cout<<v1[Idx].data<<endl;
}

The main program can be a simple one, for example:

C++
int main()
{
vector <struct bst> v1;
MakeNode(v1, 30);
Insert(v1, 20);
Insert(v1, 6);
Insert(v1, 40);
Insert(v1, 35);
Insert(v1, 16);
Insert(v1, 7);

InTrav(v1, 0);
PreTrav(v1,0);
PostTrav(v1,0);
return 0;
}

## Points of Interest

1. The same code can be used for STL deque also. I haven’t checked it for any other containers.
2. The performance will be slow as compared to raw pointers unless some vector (STL) optimizations are done. I didn't try that.
3. You can use it for small BST which you can delete in one shot without worrying about memory de-allocating.
4. Deletion of an element in BST will be updated in the next post.

## History

• First post

Written By
Architect
India
A programmer by heart since 1998. Written code in C++, Java, JavaScript, Python & Ruby, Worked on Stack Development to Web Development. Data Specialist with SQL and NoSQL DBs

 First Prev Next
 Binary search trees Member 1132977318-Jan-15 22:37 Member 11329773 18-Jan-15 22:37
 Converted code to template based OO implementation. Sharjith12-Jun-14 2:43 Sharjith 12-Jun-14 2:43
 Re: Converted code to template based OO implementation. itsdkg12-Jun-14 19:45 itsdkg 12-Jun-14 19:45
 My vote of 5 Sharjith12-Jun-14 2:16 Sharjith 12-Jun-14 2:16
 Re: My vote of 5 itsdkg12-Jun-14 19:44 itsdkg 12-Jun-14 19:44
 My Vote Of 10+ xox_c0bra_xox17-Aug-13 17:25 xox_c0bra_xox 17-Aug-13 17:25
 Wow, You people making the retarded comments on here have oviously no clue to what this code does or how it works, otherwise you wouldnt be making poor comments. Like the dude says at the end this is not as fast as a tree using pointers so that was case one. He also states this is as simple as it gets using a tree of ints there is no memory to free simply .clear() will pop the vectors off the list. The really stupid comment was about using int for a index duh a vector index is (unsigned) 0 to whatever but again people posting comments not knowing he uses int to use the -1 as a null pointer and using the standard allocator as the index there is no -1 because a vector is a 0 based dynamic array and in his code he never trys to access a vector index of -1 cause that ends the recrusion loop. Now for his demonstration and a teaching article this is brilliant simple and to the point and other then 3 typecast errors this works perfect. I also do not see a single line of code here from the people making stupid comments.
 My vote of 5 Ștefan-Mihai MOGA13-Jul-13 21:42 Ștefan-Mihai MOGA 13-Jul-13 21:42
 My vote of 2 kore3d23-Jun-13 8:51 kore3d 23-Jun-13 8:51
 Re: My vote of 2 itsdkg23-Jun-13 21:12 itsdkg 23-Jun-13 21:12
 Re: My vote of 2 kore3d23-Jun-13 22:31 kore3d 23-Jun-13 22:31
 Re: My vote of 2 itsdkg23-Jun-13 22:39 itsdkg 23-Jun-13 22:39
 where is the source? sisira20-Jun-13 10:26 sisira 20-Jun-13 10:26
 Re: where is the source? itsdkg20-Jun-13 20:17 itsdkg 20-Jun-13 20:17
 Vector Indexes are Never "int" MttD17-Jun-13 13:52 MttD 17-Jun-13 13:52
 Re: Vector Indexes are Never "int" itsdkg17-Jun-13 20:14 itsdkg 17-Jun-13 20:14
 Re: Vector Indexes are Never "int" MttD18-Jun-13 1:34 MttD 18-Jun-13 1:34
 Last Visit: 31-Dec-99 19:00     Last Update: 8-Feb-23 10:32 Refresh 1