Skip to main content

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.

Comments

Popular posts from this blog

GraphQL

GraphQL



What is GraphQL

It is a specification laid out by Facebook which proposed an alternative way to query and modify data. Think of it is an as a complimentary of REST/RPC.

Now head here and read the original graphQL documentation. It will take 2-3 hours tops but is a worthy read. This will help you build some impressions on it and help contrast against mine below:


Why use GraphQL

Core advantage

Instead of defining custom backend rpc/rest endpoints for every data-shape, graphql allows you to build a more general endpoint which give frontend/mobile engineers freedom and query and play with the data. It might be less efficient, add a bit more complexity (need for things like data-loader), harder to standardize and control client-contracts for. What it looses in complexity and control, it gains in flexibility and freedom - provided your data model is worth of a graphql-ish query How to tell if my data-model graphql-ish?Are there complex relationships between your models? Is there a need …

About me

Hi,

I'm currently working as a software developer in the logistics industry in San Francisco. 
My aim is to impact billions of people's live for the better and make the world a better place.

Cheers,
Vignesh



Backend - Tech refresher 2019

Hello there

As a software engineer, it is important to keep updating your skillsets by learning the latest programming-elements (includes paradigms, patterns, languages, tools and frameworks). This becomes a bit easy if you already working on the cutting edge of something. Even then, it is possible to go too deep and loose breadth.

I've taken upon myself to do a tech refresher every year. The intent is to read, experiment and understand these elements by spending anywhere between 4 days to 4 weeks. The ultimate goal is: "do I know most that I need to know to build a planet-scale backend tech-stack ground up"

I'll write up my learnings in posts to help myself (and maybe others) refer it.

Here is the initial list I'm thinking about:


RedisMySQL, GraphQLAurora, Mesos, KubernetesCadence, SWSCassandra, MangoDB, NoSQL, MySQL, Spanner, S<, DynDBELKFlink, Storm, Samza, SparkHadoop HDFS, Yarn, MapReduceHive, HBaseKafka, ZookeeperNW: http, Tcp, thrift, grpc, yarpc, Terraform,…