[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

Anagram Solver

I was coding out a simple string permuting function and I thought of writing out an AnagramSolver just for completion.

The Dictionary can be provided as a wordlist in the form of a text file with a word string per line. You can find several word lists here: http://wordlist.sourceforge.net/


//Sources
#include<iostream>
#include<string>
#include<fstream>
#include<map>

using namespace std;
class AnagramChecker
{
public:
map<string, bool> Dictionary;
map<string, bool> ResultList;

//Recursive string permuter
void RecurveStrPerm(string Buffer, string Test, int Cur)
{
 if (Cur >= Test.length())
 {
 if (Dictionary.count(Buffer) > 0)
 if (ResultList.count(Buffer) == 0)
 ResultList[Buffer] = true;
 return;
 }

for(int i = 0; i <= Buffer.length(); i++)
 {
 Buffer.insert(i, 1, Test[Cur]);
 RecurveStrPerm(Buffer, Test, Cur + 1);
 Buffer.erase(i, 1);
 }
}

//Build a table out of the strings
void BuildInMemDic()
{
 Dictionary.clear();
 ifstream DicReader;
 DicReader.open("WordList.txt");
 string CurrentWord= "";
 while (!DicReader.eof())
 {
 getline(DicReader, CurrentWord);
 for (int i = 0; i < CurrentWord.length(); i++)
 CurrentWord[i] = tolower(CurrentWord[i]);
 Dictionary[CurrentWord] = true;

 }
 DicReader.close();
}

//Get Result
void GetResult()
{
 cout << "\nAnagrams: \n";
 for (map<string, bool>::iterator ResultListPtr = ResultList.begin(); ResultListPtr != ResultList.end(); ResultListPtr++)
 cout << "\n" << ResultListPtr->first;

}

public:

AnagramChecker()
 {
 BuildInMemDic();
 }

void Find(string Test)
 {
 ResultList.clear();
 int cur = 0, n = Test.length();
 RecurveStrPerm("", Test, 0);
 GetResult();
 }

};

void main()
{
 string Test = "Slate";
 cout << "\nBuilding In memory Dictionary...";
 AnagramChecker AnaObj;
 cout << "\n\nInmemory dictionary built!...\n\n";

char ExitChoice = 'n';
 while (ExitChoice!='y')
 {
 cout << "\n\nEnter Anagram: ";
 cin >> Test;
 for (int i = 0; i < Test.length(); i++)
 Test[i] = tolower(Test[i]);

cout << "\n\nAnagrams for " << Test << ":\n\n";
 AnaObj.Find(Test);
 cout << "\n\nDo you want to continue: y /n :";
 cin >> ExitChoice;

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

The code is NOT optimized. It can be sped up with simple multi-threading, but I have let go of those for simplicity.

Some Binary Tree Tricks

This code can do the following:

  • Depth First Search of a Binary Tree
  • Breadth First Search of a Binary Tree
  • Finding sum of numbers formed by a path from root to leaf, in a binary tree that can contain numbers from 0-9.
  • Mirror a binary tree

I have made use of STL – Queues and vectors here.

</pre>
//Source file

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

class Node
{
public:
 int Value;
 Node *Left, *Right;

 Node(int ValueParam)
 {
 Value = ValueParam;
 Left = Right = NULL;
 }
};

class BTree
{
 private:
 Node* Root;

void _Insert(Node* Ptr, int ValueParam)
 {
 if (Ptr->Value == ValueParam) return;
 if (ValueParam < Ptr->Value)
 if (Ptr->Left == NULL) Ptr->Left = new Node(ValueParam);
 else _Insert(Ptr->Left,ValueParam);
 else if (ValueParam >Ptr->Value)
 if (Ptr->Right == NULL) Ptr->Right= new Node(ValueParam);
 else _Insert(Ptr->Right, ValueParam);
 }

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

//Mirroring a Binary Tree
 void _Mirror(Node* Ptr)
 {
 if (!Ptr) return;
 _Mirror(Ptr->Left);
 _Mirror(Ptr->Right);
 Node* Temp = Ptr->Left;
 Ptr->Left = Ptr->Right;
 Ptr->Right = Temp;
 }

public:
 BTree()
 {
 Root = NULL;
 }

void Insert(int ValueParam)
 {
 if (Root == NULL) Root = new Node(ValueParam);
 else _Insert(Root, ValueParam);
 }

void DFS()
 {
 cout << "\nDFS:\n";
 _DFS(Root);
 }
 //Breadth First Search
 queue<Node*> NodalQueue;
 void BFS()
 {
 cout << "\nBFS:\n";
 //Empty the queue
 while (!NodalQueue.empty())
 NodalQueue.pop();

if (!Root) return;
 else
 {
 cout << " - " << Root->Value;
 NodalQueue.push(Root);
 }

int CLev = 1, NLev = 0;

//Start working
 while (!NodalQueue.empty())
 {
 Node* Ptr = NodalQueue.front();
 NodalQueue.pop();
 CLev--;

&nbsp;

if (CLev <= 0)
 {
 cout << endl;
 CLev = NLev;
 NLev = 0;
 }

 if (Ptr->Left)
 {
 cout << " - " << Ptr->Left->Value;
 NodalQueue.push(Ptr->Left);
 NLev++;
 }
 if (Ptr->Right)
 {
 cout << " - " << Ptr->Right->Value;
 NodalQueue.push(Ptr->Right);
 NLev++;
 }

}
 }

//Get Numbers
 vector<vector<int>> NumberMap;
 void GetNumberMap()
 {
 cout << "\nNumberMap:\n";
 NumberMap.clear();
 queue<Node*> NumNodalQueue;
 if (!Root) return;
 else
 {
 NumNodalQueue.push(Root);
 vector<int> RootStage;
 RootStage.push_back(Root->Value);
 NumberMap.push_back(RootStage);
 }

//Start working
 int Stage = 0;
 int CLev = 1;
 int NLev = 0;
 while (!NumNodalQueue.empty())
 {
 Node* Ptr = NumNodalQueue.front();
 vector<int> NewStage;
 NumNodalQueue.pop();
 CLev--;
 if (CLev<=0)
 {
 Stage++;
 NumberMap.push_back(NewStage);
 CLev = NLev;
 NLev = 0;
 }
 if (Ptr->Left)
 {
 NumberMap[Stage].push_back(Ptr->Left->Value);
 NumNodalQueue.push(Ptr->Left);
 NLev++;
 }
 if (Ptr->Right)
 {
 NumberMap[Stage].push_back(Ptr->Right->Value);
 NumNodalQueue.push(Ptr->Right);
 NLev++;
 }
 }

//Numbermap is ready
 //Calcualte combinations from NumberMap
 NumberMap.pop_back();
 GetCombinations();
 }

void GetCombinations()
 {
 GlobalTot = 0;
 RecCombi();
 }

long int fnPow(int Base, int Power)
 {
 if (Power == 0) return 1;
 return Base*fnPow(Base, Power - 1);
 }

long int GlobalTot = 0;
 void RecCombi(vector<int>* Temp=NULL, int Stage=0)
 {
 if (Temp && Stage == NumberMap.size())
 {
 cout << "\n";
 for (int i = 0; i < Temp->size(); i++)
 {
 long int pval = fnPow(10, (Temp->size() - 1 - i));
 GlobalTot += (*Temp)[i]*(pval);
 cout << " " << (*Temp)[i];
 }
 cout << "\n";
 //Adding number to Global
 }
 if (Stage < NumberMap.size())
 {
 if (!Temp) Temp = new vector<int>();
 for (int i = 0; i < NumberMap[Stage].size(); i++)
 {
 Temp->push_back(NumberMap[Stage][i]);
 RecCombi(Temp, Stage + 1);
 Temp->pop_back();
 }
 }
 }

void Mirror()
 {
 _Mirror(Root);
 cout << "\nTree Mirrored\n";
 }

};

int main()
{
 BTree MyTree;

MyTree.Insert(6);
 MyTree.Insert(2);
 MyTree.Insert(10);
 MyTree.Insert(0);
 MyTree.Insert(4);
 MyTree.Insert(8);
 MyTree.Insert(15);
 MyTree.Insert(-1);
 MyTree.Insert(1);
 MyTree.Insert(3);
 MyTree.Insert(5);
 MyTree.Insert(7);
 MyTree.Insert(9);
 MyTree.Insert(12);
 MyTree.Insert(20);
 MyTree.DFS();
 MyTree.BFS();
 MyTree.Mirror();
 MyTree.DFS();
 MyTree.BFS();
 MyTree.GetNumberMap();

cout << "\nGloabl total =" << MyTree.GlobalTot << endl;
 cout << "\n\nEnd of code\n\n";
 system("pause");

return 0;
}

&nbsp;
<pre>

Please note: The third problem (finding sum of numbers) does not require a binary search tree which has been used here. A simple binary tree would do. But the code would be the same whether the tree is a BST or not.

Finding the square root (of a perfect square) using binary search c#

Well, the logic is pretty straightforward. We start a binary search from a range of 0 to NUM, where NUM is the number whose root we are looking for. Each time, we calculate the middle item of the range and see if it is the square root. If not, we search further either in the right side or the left side of the mid item depending on whether the mid^2 is lesser or greater than NUM.

double GetRoot(double Num,double High=0, double Low=0)
{
if(High&lt;Low || High-Low==1) return -1; //End case
if(High==Low &amp;&amp; Low==0) High=Num; //Start case
int Mid= Low+((High-Low)/2);
if(Mid*Mid==Num) return Mid;
else
{
if(Mid*Mid&gt;Num) return GetRoot(Num,Mid,Low);
else if(Mid*Mid&lt;Num) return GetRoot(Num,High,Mid);
}
}

If you have thoughts/ suggestions, post em on comments.

N Queens problem

Well, I can’t possibly have an ‘algorithm of the day’ thread without solving the all famous N QUEENs problem.

Problem description:

Place the maximum amount of Queens on an N by N chess board and print the possible arrangements

Solution:

We will be placing 1 queen at a time per row. We would start  from the left most end of the row and move 1 step to the right if there is a collision. We keep doing this till we find a spot that does poses no collisions. If there is no such spot, then one of the previous queens must be moved elsewhere.

Code:

//NQueen problem
#include
using namespace std;

int N;
int Pos=0;

void NQueenDroid(int Board[100], int Remaining)
{
	if(Remaining==0)
	{
		//found a solution
		cout&lt;&lt;endl;
		for(int i=0;i&lt;N;i++) cout&lt;&lt;Board[i]&lt;&lt;" - "; 
		Pos++;
		return;
	}

	int Cur= N-Remaining; //placement of current queen
	for(int i=0;i&lt;N;i++)
	{
		bool IsColliding= false;
		for(int k=0;k&lt;Cur;k++) 
		{
                        //Collision in columns
			if(Board[k]==i) {IsColliding=true; break;} 
			if(abs(Board[k]-i)==abs(Cur-k)) 
                                  {IsColliding=true; break;}  //Collision in diagonals
		}		
		if(IsColliding) continue;
		Board[Cur]=i; //place queen
		NQueenDroid(Board,Remaining-1);
	}
}

int main()
{

	N=0;
	cout&lt;&lt;"Enter the board size :"; 	
        cin&gt;&gt;N;
	int Board[100]={0};
	NQueenDroid(Board,N);

	//End of code
	return 0;
}