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:
- 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:
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);
}
The full code is as follows:
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;
}
Vignesh Murugesan's Blog 