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.

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