Click here to Skip to main content
15,867,453 members
Articles / Programming Languages / C++

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

Rate me:
Please Sign up or sign in to vote.
4.86/5 (12 votes)
20 Jun 2013CPOL2 min read 104K   842   16   16
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++
void MakeNode(vector<struct> &v1, int aData)
{
    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(aData <= v1[currentIdx].data)
        {
            if( v1[currentIdx].leftIdx == -1)
            {
                setleft(v1, currentIdx, aData);
                break;
            }
            else
                currentIdx = v1[currentIdx].leftIdx;
        }
        else
        {
            if(v1[currentIdx].rightIdx == -1)
            {
                setright(v1, currentIdx, aData);
                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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Architect
India 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

Comments and Discussions

 
QuestionBinary search trees Pin
Member 1132977318-Jan-15 21:37
Member 1132977318-Jan-15 21:37 
SuggestionConverted code to template based OO implementation. Pin
Sharjith12-Jun-14 1:43
professionalSharjith12-Jun-14 1:43 
I thought someone may like to use it in a truly object oriented way so just reimplemented your code using a template class...

C++
// VectorBinaryTree.h
#pragma once

#include <iostream>
#include <vector>
using namespace std;

template<class T>
class VectorBinaryTree
{
public:

	VectorBinaryTree(T data)
	{
		makeNode(data);
	}

	~VectorBinaryTree()
	{
                v1.clear();
	}

	void insert(T aData)
	{
		if(v1.size() == 0)
		{
			cout << "Note is not made yet. MakeNode first..." << endl;
			return;
		}
		unsigned int currentIdx = 0;
		while ( currentIdx < v1.size() )
		{
			if(aData <= v1[currentIdx].data)
			{
				if( v1[currentIdx].leftIdx == -1)
				{
					setleft(currentIdx, aData);
					break;
				}
				else
					currentIdx = v1[currentIdx].leftIdx;
			}
			else
			{
				if(v1[currentIdx].rightIdx == -1)
				{
					setright(currentIdx, aData);
					break;
				}
				else
					currentIdx = v1[currentIdx].rightIdx;
			}
		}
	}

	void traverseInOrder(unsigned int Idx)
	{
		if(v1[Idx].leftIdx != -1)
			traverseInOrder(v1[Idx].leftIdx );
		cout << v1[Idx].data << endl;
		if( v1[Idx].rightIdx != -1)
			traverseInOrder(v1[Idx].rightIdx);
	}

	void traversePreOrder(unsigned int Idx)
	{
		cout << v1[Idx].data << endl;
		if(v1[Idx].leftIdx != -1)
			traversePreOrder(v1[Idx].leftIdx );
		if( v1[Idx].rightIdx != -1)
			traversePreOrder(v1[Idx].rightIdx);
	}
	void traversePostOrder(unsigned int Idx)
	{
		if(v1[Idx].leftIdx != -1)
			traversePostOrder(v1[Idx].leftIdx );
		if( v1[Idx].rightIdx != -1)
			traversePostOrder(v1[Idx].rightIdx);
		cout << v1[Idx].data << endl;
	}

private:

	void makeNode(T aData)
	{
		bst b1 = { aData, -1, -1 };
		v1.push_back(b1);
	}

	void setleft(int currIndex, T aData)
	{
		unsigned int leftIndex = v1.size();
		v1[currIndex].leftIdx = leftIndex;
		struct bst b1 = { aData, -1, -1 };
		v1.push_back(b1);
	}

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

private:
	struct bst
	{
		T data;
		int leftIdx;
		int rightIdx;
	};

	vector<bst> v1;
};


C++
// main.cpp
#include "VectorBinaryTree.h"

int _tmain(int argc, _TCHAR* argv[])
{
	
	VectorBinaryTree<int> t(30);

	t.insert(20);
	t.insert(6);
	t.insert(40);
	t.insert(35);
	t.insert(16);
	t.insert(7);

	t.traverseInOrder(0);
	t.traversePreOrder(0);
	t.traversePostOrder(0);

	return 0;
}

RegardsSmile | :)
N. Sharjith


modified 12-Jun-14 8:08am.

GeneralRe: Converted code to template based OO implementation. Pin
itsdkg12-Jun-14 18:45
itsdkg12-Jun-14 18:45 
GeneralMy vote of 5 Pin
Sharjith12-Jun-14 1:16
professionalSharjith12-Jun-14 1:16 
GeneralRe: My vote of 5 Pin
itsdkg12-Jun-14 18:44
itsdkg12-Jun-14 18:44 
NewsMy Vote Of 10+ Pin
xox_c0bra_xox17-Aug-13 16:25
xox_c0bra_xox17-Aug-13 16:25 
GeneralMy vote of 5 Pin
Ștefan-Mihai MOGA13-Jul-13 20:42
professionalȘtefan-Mihai MOGA13-Jul-13 20:42 
GeneralMy vote of 2 Pin
kore3d23-Jun-13 7:51
kore3d23-Jun-13 7:51 
GeneralRe: My vote of 2 Pin
itsdkg23-Jun-13 20:12
itsdkg23-Jun-13 20:12 
GeneralRe: My vote of 2 Pin
kore3d23-Jun-13 21:31
kore3d23-Jun-13 21:31 
GeneralRe: My vote of 2 Pin
itsdkg23-Jun-13 21:39
itsdkg23-Jun-13 21:39 
Questionwhere is the source? Pin
sisira20-Jun-13 9:26
sisira20-Jun-13 9:26 
AnswerRe: where is the source? Pin
itsdkg20-Jun-13 19:17
itsdkg20-Jun-13 19:17 
SuggestionVector Indexes are Never "int" Pin
MttD17-Jun-13 12:52
MttD17-Jun-13 12:52 
GeneralRe: Vector Indexes are Never "int" Pin
itsdkg17-Jun-13 19:14
itsdkg17-Jun-13 19:14 
GeneralRe: Vector Indexes are Never "int" Pin
MttD18-Jun-13 0:34
MttD18-Jun-13 0:34 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.