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.

[code language="cpp"]</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>
[/code]

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.