Skip to main content

[Binary Tree] Convert a List to a Binary Search Tree of minimal height

The Problem is to create a binary search tree of minimal possible height from a given list of values. The algorithm for this is quite simple:

  1. Sort the items (ascending as well as descending order would do)

  2. Use divide and conquer approach for selecting the items for insertion from the array. Given the list, insert its MID item. Then Partition the list into two: 1 list with items less than the MID and another list with items more than MID and recursively process those lists.

  3. The crux of this function is as follows:


[code language="cpp"]
void _InsertListRec(int *Arr, int StartIndex, int EndIndex)
{
if (StartIndex > EndIndex) return;
int Mid = 0;
Mid = StartIndex + (EndIndex - StartIndex) / 2;
Insert(Arr[Mid]);
_InsertListRec(Arr, StartIndex, Mid - 1);
_InsertListRec(Arr, Mid + 1, EndIndex);
}

[/code]

The full code is as follows:

[code language="cpp"]
class TreeNode
{
public:
TreeNode *Left, *Right;
int NodalValue;

TreeNode(int ValueParam)
{
NodalValue = ValueParam;
Left = Right = NULL;
}
};

 

class BinarySearchTree
{
TreeNode* Root;

void _Insert(TreeNode* Ptr, int ValueParam)
{
//if (!Ptr) return;
if (Ptr->NodalValue == ValueParam) return;
if (ValueParam < Ptr->NodalValue)
{
if (Ptr->Left == NULL) Ptr->Left = new TreeNode(ValueParam);
else _Insert(Ptr->Left, ValueParam);
}
else
{
if (Ptr->Right == NULL) Ptr->Right = new TreeNode(ValueParam);
else _Insert(Ptr->Right, ValueParam);
}
return;
}

void _DFS(TreeNode* Ptr)
{
if (!Ptr) return;
_DFS(Ptr->Left);
cout << " " << Ptr->NodalValue;
_DFS(Ptr->Right);
}

public:
BinarySearchTree()
{
Root = NULL;
}

void Insert(int ValueParam)
{
if (!Root)
{
Root = new TreeNode(ValueParam);
return;
}
_Insert(Root, ValueParam);
}

void DFS()
{
cout << "\nDFS:\n";
_DFS(Root);
}

queue<TreeNode*> NodalQueue;
void BFS()
{
cout << "\nBFS:\n";
if (!Root) return;
while (!NodalQueue.empty())
NodalQueue.pop();
cout << Root->NodalValue << "\n";
NodalQueue.push(Root);
int CLev = 1, NLev = 0;
while (NodalQueue.size() > 0)
{
TreeNode *Ptr = NodalQueue.front();
NodalQueue.pop();
CLev--;
if (Ptr->Left){
cout << Ptr->Left->NodalValue<<" ";
NodalQueue.push(Ptr->Left);
NLev++;
}
if (Ptr->Right)
{
cout << Ptr->Right->NodalValue<<" ";
NodalQueue.push(Ptr->Right);
NLev++;
}
if (!CLev)
{
cout << "\n";
CLev = NLev;
NLev = 0;
}
}

}
void _ClearTree(TreeNode *Ptr)
{
if (!Ptr) return;
if (Ptr->Left){ _ClearTree(Ptr->Left); delete Ptr; }
if (Ptr->Right){ _ClearTree(Ptr->Right); delete Ptr; };
}
void ClearTree()
{
//Post order node deltion
_ClearTree(Root);
Root = NULL;
}

void _InsertListRec(int *Arr, int StartIndex, int EndIndex)
{
if (StartIndex > EndIndex) return;
int Mid = 0;
Mid = StartIndex + (EndIndex - StartIndex) / 2;
Insert(Arr[Mid]);
_InsertListRec(Arr, StartIndex, Mid - 1);
_InsertListRec(Arr, Mid + 1, EndIndex);
}

enum INSERT_OPTION
{
DEFAULT=0,
MIN_HEIGHT=1
};

void InsertList(int *Arr, int Size, INSERT_OPTION CallOption= DEFAULT)
{
ClearTree();

switch (CallOption)
{

case BinarySearchTree::MIN_HEIGHT:
//Sort the list
//->Here assuming that the list is already sorted
_InsertListRec(Arr, 0, Size-1);
break;

case BinarySearchTree::DEFAULT:
for (int i = 0; i < Size; i++)
Insert(Arr[i]);
break;

default:
cout << "\nInvalid Call option\n";
break;
}
}
};

&nbsp;

int main()
{
int Array[] = { 1, 3, 4, 5, 6, 8, 10 };
BinarySearchTree test;

test.InsertList(Array, 7);
test.DFS();
test.BFS();
cout << "\n\nCreating minumum tree:\n";
test.InsertList(Array, 7, BinarySearchTree::MIN_HEIGHT);
test.DFS();
test.BFS();

cout << "\n\nEnd of code";
system("pause");

return 0;
}

[/code]

Comments

Popular posts from this blog

GraphQL

GraphQL



What is GraphQL

It is a specification laid out by Facebook which proposed an alternative way to query and modify data. Think of it is an as a complimentary of REST/RPC.

Now head here and read the original graphQL documentation. It will take 2-3 hours tops but is a worthy read. This will help you build some impressions on it and help contrast against mine below:


Why use GraphQL

Core advantage

Instead of defining custom backend rpc/rest endpoints for every data-shape, graphql allows you to build a more general endpoint which give frontend/mobile engineers freedom and query and play with the data. It might be less efficient, add a bit more complexity (need for things like data-loader), harder to standardize and control client-contracts for. What it looses in complexity and control, it gains in flexibility and freedom - provided your data model is worth of a graphql-ish query How to tell if my data-model graphql-ish?Are there complex relationships between your models? Is there a need …

About me

Hi,

I'm currently working as a software developer in the logistics industry in San Francisco. 
My aim is to impact billions of people's live for the better and make the world a better place.

Cheers,
Vignesh



Backend - Tech refresher 2019

Hello there

As a software engineer, it is important to keep updating your skillsets by learning the latest programming-elements (includes paradigms, patterns, languages, tools and frameworks). This becomes a bit easy if you already working on the cutting edge of something. Even then, it is possible to go too deep and loose breadth.

I've taken upon myself to do a tech refresher every year. The intent is to read, experiment and understand these elements by spending anywhere between 4 days to 4 weeks. The ultimate goal is: "do I know most that I need to know to build a planet-scale backend tech-stack ground up"

I'll write up my learnings in posts to help myself (and maybe others) refer it.

Here is the initial list I'm thinking about:


RedisMySQL, GraphQLAurora, Mesos, KubernetesCadence, SWSCassandra, MangoDB, NoSQL, MySQL, Spanner, S<, DynDBELKFlink, Storm, Samza, SparkHadoop HDFS, Yarn, MapReduceHive, HBaseKafka, ZookeeperNW: http, Tcp, thrift, grpc, yarpc, Terraform,…