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

&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;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s