Click here to Skip to main content
15,500,990 members
Articles / Programming Languages / C
Posted 4 Sep 2013

Tagged as


24 bookmarked

Fast Binary Search Trees (BST) using Arrays

Rate me:
Please Sign up or sign in to vote.
3.91/5 (7 votes)
27 Apr 2016CPOL3 min read
This tip explains the usage of arrays for creating Fast binary search trees.


Creating a tree data structure involves lots of pointer manipulation and memory overhead. In my article, Creating BST using STL vector, I tried to get rid of pointer manipulations. However, the STL based BST data structure makes it slow and unusable for large data. In this tip, I will be showing how to create a fast and efficient binary search tree using C/C++ arrays. The only condition is that we need to know the maximum number of elements this data structure will have in its lifetime.

This implementation is different than normal array index calculation of 2*n + 1 and 2*n + 2 for left and right child. In this example, the elements will be added in sequence and there left and right indexes are stored in BST data structure.


Creating binary search trees using C/C++ arrays is not a new idea, but the algorithm to calculate the left and right sub child makes array size much more than number of elements.

Consider the creation of this BST example:

  • Insert (50), since this is the first element, it is added at index [0] and becomes the root element.
  • Insert (30) which is left sub child of root and array index will be [2*n + 1] = [2 * 0 + 1] = [1]
  • Insert (60) which is right sub child of root and array index will be [2*n + 2] = [2*0 + 2] = [2]
  • Insert (15), this will be left sub child of (30) and index will be [2*n + 1] = [2*1 + 1] = [3]
  • Insert (70), this will be the right sub child of (60) and index will be [2*n + 2] = [2*2 + 2] = [6]

    In this case, an array of size = 7 is required for 5 elements. This will grow as we keep on including elements. Let me also explain that a perfectly balanced binary search tree doesn't waste array elements, so this example will be useful for real life scenarios where order of elements may not result in perfectly balanced binary trees.

Using the Code

First, I will define the maximum array elements our binary search tree can hold.

#define MAX_ELEMS 100

Then I'll define the binary search tree data structures. normal data structures are pointer based with pointer to left and right sub child. Since we're dealing with the array indexes, I will define left and right sub child as array indexes to make this code to be as generic as possible.

struct bst
	int data;
	int lindex;
	int rindex;

Here I'm defining functions for creating the tree and inserting in left and right child. These functions assume that the node is already created.

void MakeNode(struct bst * tree, int data)
	tree->data = data;
	tree->lindex = tree->rindex = -1;

void Insertleft( struct bst *tree, int data)
	MakeNode(tree, data);

void Insertright( struct bst * tree, int data)
	MakeNode(tree, data);

Now, here is the insert function which will add binary search tree elements one by one in its appropriate place. The index assignments will be done in this function itself.

void Insert(struct bst * tree, int treeIndex, int data)
	int baseIndex = 0;
	while(baseIndex <= treeIndex)
		if(data <= tree[baseIndex].data)
			if(tree[baseIndex].lindex == -1)
				tree[baseIndex].lindex = treeIndex;
				Insertleft(&tree[treeIndex], data);
				baseIndex = tree[baseIndex].lindex;

		else // data is > tree[baseIndex].data
			if(tree[baseIndex].rindex == -1)
				tree[baseIndex].rindex = treeIndex;
				Insertright(&tree[treeIndex], data);
				baseIndex = tree[baseIndex].rindex;

Since we have the trees, we need to traverse the trees also. I'm writing the functions to traverse the trees in in-order, pre-order, and post-order manner.

void Intrav(struct bst * tree, int index)
	if(tree[index].lindex != -1)
		Intrav( tree, tree[index].lindex );
	cout<<"DataIn ="<<tree[index].data<<endl;
	if(tree[index].rindex != -1)
		Intrav( tree, tree[index].rindex );

void Pretrav(struct bst * tree, int index)
	cout<<"DataPre ="<<tree[index].data<<endl;
	if(tree[index].lindex != -1)
		Pretrav( tree, tree[index].lindex );
	if(tree[index].rindex != -1)
		Pretrav( tree, tree[index].rindex );

void Posttrav(struct bst * tree, int index)
	if(tree[index].lindex != -1)
		Posttrav( tree, tree[index].lindex );
	if(tree[index].rindex != -1)
		Posttrav( tree, tree[index].rindex );
	cout<<"DataPost ="<<tree[index].data<<endl;

Here is a simple main function to demonstrate the functionality of the tree. The only thing to take into account is that the array index is incremented after addition of each element.

int main()
	struct bst tree[MAX_ELEMS];
	memset(tree, 0, sizeof(tree));
	int treeIndex = 0;

	MakeNode(&tree [treeIndex], 50);
	Insert(tree, treeIndex, 10);
	Insert(tree, treeIndex, 60);
	Insert(tree, treeIndex, 25);
	Insert(tree, treeIndex, 30);
	Insert(tree, treeIndex, 92);
	Insert(tree, treeIndex, 15);
	Insert(tree, treeIndex, 67);
	Intrav(tree, 0);
	Posttrav(tree, 0);

	return 0;

Points of Interest

  1. A fast BST
  2. Less penalty with unbalanced trees as compared to pointer based unbalanced trees
  3. Maximum size has to be known in the beginning, however you can tweak with re-alloc based logics


  • First version


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

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

GeneralQuite good idea. Pin
Member 70399929-Mar-17 4:00
MemberMember 70399929-Mar-17 4:00 
Questionshared memory Pin
bling28-Apr-16 9:39
Memberbling28-Apr-16 9:39 
QuestionSadly this Tree is not friendly to deletes. Will get very unbalanced. Pin
Spundun Bhatt12-Feb-15 13:08
MemberSpundun Bhatt12-Feb-15 13:08 
AnswerRe: Sadly this Tree is not friendly to deletes. Will get very unbalanced. Pin
itsdkg16-May-15 20:49
Memberitsdkg16-May-15 20:49 
GeneralRe: Sadly this Tree is not friendly to deletes. Will get very unbalanced. Pin
FrankLaPiana28-Apr-16 13:30
MemberFrankLaPiana28-Apr-16 13:30 
Question[My vote of 2] Fast but inefficient Pin
YvesDaoust9-Sep-13 0:33
MemberYvesDaoust9-Sep-13 0:33 
AnswerRe: [My vote of 2] Fast but inefficient Pin
itsdkg11-Sep-13 18:29
Memberitsdkg11-Sep-13 18:29 
Dear Sir

Please go through the article again. its fast as compared to pointer based data structure. This is not an algorithm of node balancing so please dont compare this with something which this article doesn't intend to do.

Questionexample main Pin
Member 100596696-Sep-13 7:32
MemberMember 100596696-Sep-13 7:32 
AnswerRe: example main Pin
itsdkg11-Sep-13 18:31
Memberitsdkg11-Sep-13 18:31 
QuestionCode ? Pin
_Flaviu4-Sep-13 23:50
Member_Flaviu4-Sep-13 23:50 
AnswerRe: Code ? Pin
itsdkg5-Sep-13 0:14
Memberitsdkg5-Sep-13 0:14 

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.