Go lang: Return True specified Pct% of time

When writing test for state machines, I came across a need for a helper that would all call flow into a path some percentage% of times.

Eg:

func TestSelfDrivingCar_BasicRun(t *testing.T) {
    car := NewMockCar(t)
    car.Start()
    if (/* 50% probability that this will happen */) {
        car.SimulateLidarFailure()        
    } else if /* 25% probability that this will happen */ {
        car.SimulateVisionFailure()
    } else {
        /* 25% probability that this will happen*/
        car.SimulateGearBoxFailure()
    }
    car.VerifySafeTrajectory()
}

You can write a small Go helper like this:

package testutils

import (
  "math/rand"
  "time"
)

// Odds returns True to pct% number of Check() calls
type Odds interface {
  Check() bool
}

// odds returns `true` pct% of times
type odds struct {
  randgen *rand.Rand
  pct     int
}

// NewOdds returns a odds instance with the given percent vaule
func NewOdds(pct int) Odds {
  src := rand.NewSource(time.Now().UnixNano())
  return &odds{
    randgen: rand.New(src),
    pct:     pct,
  }
}

// Check returns True to pct% of Check() calls
func (o *odds) Check() bool {
  return o.randgen.Intn(100) < o.pct
}

Usage:

func TestSelfDrivingCar_BasicRun(t *testing.T) {
    odds50pct, odds25pct := NewOdds(50), NewOdds(25)
    car := NewMockCar(t)
    car.Start()
    if odds50pct.Check() {
        car.SimulateLidarFailure()        
    } else if odds25pct.Check() {
        car.SimulateVisionFailure()
    } else {
        /* 25% probability that this will happen*/
        car.SimulateGearBoxFailure()
    }
    car.VerifySafeTrajectory()
}

ps: No, I don’t work on self-driving cars – this is just a code sample ūüôā


			

[BackTracking] [C++] Permutations of given string


// STRING PERMUTATIONS
void swap(char &a, char &b)
{
a = a^b;
b = a^b;
a = a^b;
}
void _strPermute(char *s, int n, int pos)
{
if (pos == n-1)
{
cout << s << endl;
return;
}
for (int i = pos + 1; i < n; i++)
{
swap(s[pos], s[i]);
_strPermute(s, n, pos + 1);
swap(s[pos], s[i]);
}
}
void printStringPermutations(char *s, int n)
{
if (n < 2) return;
_strPermute(s, n, 0);
}

[TIP] How to unselect all items in Wunderlist

I’ve been using Wunderlist for some time. It is a great tool especially when it comes to group¬†shopping. I’ve seen a lot of people posting questions on how to “group unselect” items on wunderlist. It was even on¬†¬†the¬†“most requested feature-list”.

I found a way to do this in 3 super quick steps- so sharing it below:

  1. Press CTRL+A to select all items (Ensure the completed items are hidden Рthis should be default) and then Press CTRL+D to mark them as completed.
  2. Now all items should be hidden since they are marked as complete. Now click ‘Show marked items’ to show them all.
  3. CTRL+A to select all and CTRL+D to mark them incomplete.

This has really helped me with my grocery lists since I would need to reset it before the next purchase.

WildCard Matching algorithm

The logic is quite simple. We do the following 3 basic checks before we do the comparison:

  1. Check for nulls and return if either of the String or Pattern is null
  2. Check if we have reached the end of string. If so, return true
  3. If either of string or pattern are left over, return false
  4. One case that we need to explicitly handle is when string is EMPTY and pattern is made solely of one or more *s.

Comparison:

  1. If it is a char or ?, skip 1 ahead in both string and pattern
  2. If it is a *, return the result of
    • string+1,pattern+1 – For handling multiple *s
    • string,pattern+1 ¬† ¬† – For handling null *
    • string+1,pattern ¬† ¬† – For handling multi-char *

The actual code is pretty simple. The following code has a complexity of around 2^n for an sized string.

bool OnlyAskterisk(char* Pattern)
{
 if (*Pattern == '\0') return true;
 if (*Pattern != '*') return false;
 else return OnlyAskterisk(Pattern + 1);
}

bool isMatch(char *String, char *Pattern)
{
 //Base case checks
 if (*String=='\0' &&OnlyAskterisk(Pattern)) return true;
 if (!String || !Pattern) return false;
 if (*String == '\0' && *Pattern == '\0') return true;
 if (*String == '\0' || *Pattern == '\0') return false; //Tricky case which is used to eliminate stack overflows with * variable

//Actual comparisons
 if ((*String == *Pattern) || (*Pattern == '?'))
 return isMatch(String + 1, Pattern + 1);
 //Multimatch- StringMoves, No Match-PatternMoves SingleMatch- BothMove. Single match is to handle last char being *
 if (*Pattern == '*') return (isMatch(String + 1, Pattern) || isMatch(String + 1, Pattern + 1) || isMatch(String, Pattern + 1));
 return false;
}

Hash Table in C++

I have implemented a simple hash-table in C++. I have used the modified version of Bernstein’s Hash function for it. For more on the Bernstein’s hash, read this¬†http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx

 

 

</pre>
class HashTable
{
 typedef long long unsigned int HashValueType;
 typedef int KeyType;
 int BucketSize;
 vector<vector<KeyType>> Buckets;

 void InsertAtBucket(int ValueParam, int BucketId)
 {
 Buckets[BucketId].push_back(ValueParam);
 }
 bool FindAtBucket(int ValueParam, int BucketId)
 {
 if (Buckets[BucketId].size() <= 0) return false;
 vector<KeyType>::iterator Ptr = Buckets[BucketId].begin();
 while (Ptr != Buckets[BucketId].end())
 {
 if ((*Ptr) == ValueParam) return true;
 Ptr++;
 }
 return false;
 }
 HashValueType HashFunction(void* Input, int Size)
 {
 HashValueType HValue = 0;
 for (int i = 0; i < Size; i++)
 HValue = (33 * HValue) + ((char*)Input)[i];
 return HValue;;
 }
public:

HashTable(int BucketSizeParam = 100)
 {
 BucketSize = BucketSizeParam;
 Buckets.clear();
 for (int i = 0; i < BucketSize; i++)
 Buckets.push_back(vector<KeyType>());
 }
 void Insert(int ValueParam)
 {
 //BucketSize
 if (!LookUp(ValueParam))
 InsertAtBucket(ValueParam, HashFunction(&ValueParam,sizeof(int))%BucketSize);
 }

bool LookUp(int ValueParam)
 {
 return FindAtBucket(ValueParam, HashFunction(&ValueParam, sizeof(int))%BucketSize);
 }
};
<pre>

Priority Queue implementation using MaxHeap

The Priority Queue with a MaxRemove() interface can be implemented using a MaxHeap which is a complete binary tree that maintains the maximum (here it would be the maximum of the priority values) of the elements that it contains at its root.

The Code is super simple and is as follows:


PriorityQueue(int CapacityParam)
 {
 Data = (int*)malloc(CapacityParam*sizeof(int));
 ToH = -1;
 Capacity = CapacityParam;
 }

void Display()
 {
 cout << "\nList:\n";
 for (int iter = 0; iter <= ToH; iter++)
 cout << " " << Data[iter];
 }

void HeapifyUp(int Position)
 {
 if (Position < 1) return;
 if (Data[Position]>Data[(Position - 1) / 2])
 {
 Swap(&(Data[Position]), &(Data[(Position - 1) / 2]));
 HeapifyUp((Position - 1) / 2);
 }
 }

bool Insert(int ParamValue)
 {
 if (ToH >= Capacity - 1) return false; //QueueOverflow
 Data[++ToH] = ParamValue;
 HeapifyUp(ToH);
 return true;
 }

void HeapifyDown(int Position)
 {
 if (2 * Position + 1 > ToH) return;
 if (2 * Position + 2 <= ToH)
 {
 //LR exists
 if (Data[2 * Position + 1] > Data[2 * Position + 2])
 {
 //L
 if (Data[2 * Position + 1] > Data[Position]) Swap(&(Data[2 * Position + 1]) ,& (Data[Position]));
 HeapifyDown(2 * Position + 1);
 }
 else
 {
 //R
 if (Data[2 * Position + 2] > Data[Position]) Swap(&(Data[2*Position+2]), &(Data[Position]));
 HeapifyDown(2 * Position + 2);
 }
 }
 else
 {
 //Only L exists
 //L
 if (Data[2 * Position + 1] > Data[Position]) Swap(&(Data[2 * Position + 1]), &(Data[Position]));
 HeapifyDown(2 * Position + 1);
 }
 }

void SortDump()
 {
 int SortToH = ToH;
 while (ToH >= 0)
 {
 Swap(&(Data[0]), &(Data[ToH]));
 --ToH;
 HeapifyDown(0);
 }
 ToH = SortToH;
 Display();
 }
};

void FillArrayWithRand(int *Array, int Size)
{
 if (!Array || Size<=0) return;
 for (int i = 0; i < Size; i++)
 Array[i] = (rand() % 10);
}
int main()
{
 //Dont allow 0 in the tree for CommonAncestor problem

const int DataSetSize = 9999;
 int *RandArray = (int*)malloc(DataSetSize * sizeof(int));
 FillArrayWithRand(RandArray, DataSetSize);
 cout << "\nRandom Array:\n";
 for (int i = 0; i < DataSetSize; i++)
 cout<<" "<<RandArray[i];

PriorityQueue test(DataSetSize);
 for (int i = 0; i < DataSetSize; i++)
 test.Insert( RandArray[i]);
 test.Display();
 test.SortDump();

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

return 0;
}

&nbsp;

InFix to PostFix and PreFix conversion [C++]

To Convert from InFix to Postfix:

  • Print out constants from InFix directly onto the Postfix output
  • For operators, insert them into a stack
  • ¬† ¬† Before insertion, make sure to pop out (and print to Postfix output) all operator that have higher precedence than that of the operator currently being inserted.
  • After the entire Infix is processed, flush the stack (if it is not empty) onto the Postfix output

-In case of InFix to Prefix, we must start processing the string from the RIGHT most to LEFT most instead of the usual LEFT to RIGHT.

-This code can handle only numbers from 0-9 (single digit) and +-*/ operators.

//Evaluate the given expression
#include<iostream>
#include<stack>
#include<vector>
using namespace std;

//Only single digit numbers permitted

int GetPrecedence(char op)
{
 switch (op)
 {
 case '+':
 case '-':
 return 1;
 case '*':
 case '/':
 default:
 return 2;
 }
}
char* ConvertInorderToPreOrder(char* InOrderExp, int Size)
{
 stack<char> Operators;
 vector<char> PostOrderResult;
 for (int i = Size-1; i >=0; i--)
 if (InOrderExp[i] >= '0'&& InOrderExp[i] <= '9')
 PostOrderResult.push_back(InOrderExp[i]);
 else
 {
 while (!Operators.empty() && GetPrecedence(Operators.top()) >= GetPrecedence(InOrderExp[i]))
 {
 PostOrderResult.push_back(Operators.top());
 Operators.pop();
 }
 Operators.push(InOrderExp[i]);
 }
 while (!Operators.empty())
 {
 PostOrderResult.push_back(Operators.top());
 Operators.pop();
 }
 char *ResultString = (char*)malloc(sizeof(char)*PostOrderResult.size()+1);
 memset(ResultString, 0, sizeof(char)*(PostOrderResult.size() + 1));
 for (int i = 0; i < PostOrderResult.size(); i++)
 ResultString[i] = PostOrderResult[i];
 ResultString[PostOrderResult.size()] = '\0';
 _strrev(ResultString);
 return ResultString;
}
char* ConvertInorderToPostOrder(char* InOrderExp, int Size)
{
 stack<char> Operators;
 vector<char> PostOrderResult;
 for (int i = 0; i < Size; i++)
 if (InOrderExp[i] >= '0'&& InOrderExp[i] <= '9')
 PostOrderResult.push_back(InOrderExp[i]);
 else
 {
 while (!Operators.empty() && GetPrecedence(Operators.top()) >= GetPrecedence(InOrderExp[i]))
 {
 PostOrderResult.push_back(Operators.top());
 Operators.pop();
 }
 Operators.push(InOrderExp[i]);
 }
 while (!Operators.empty())
 {
 PostOrderResult.push_back(Operators.top());
 Operators.pop();
 }
 char *ResultString = (char*)malloc(sizeof(char)*PostOrderResult.size()+1);
 memset(ResultString, 0, sizeof(char)*(PostOrderResult.size()+1));
 for (int i = 0; i < PostOrderResult.size(); i++)
 ResultString[i] = PostOrderResult[i];
 ResultString[PostOrderResult.size()] = '\0';
 return ResultString;
}

int main()
{

char InExp[] = "2+3*7-5*2-4/2*5+1-4+2/2+1";
 cout << "\nInput: " << InExp;
 cout << "\n\n";
 cout << "\n\PostFix = " << ConvertInorderToPostOrder(InExp, strlen(InExp));
 cout << "\n\PreFix = " << ConvertInorderToPreOrder(InExp, strlen(InExp));
 cout << "\n\nEnd of code\n\n";
 system("pause");
 return 0;
}

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

&nbsp;

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

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.