This code can do the following:

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

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;

}

<pre>

[/code]

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

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;

}

<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.
## Comments

## Post a Comment