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:

[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;

}

}

};

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]

- Sort the items (ascending as well as descending order would do)
- 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.
- 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;

}

}

};

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

## Post a Comment