# Trees to Binary Trees

picture credits :http://turnoff.us/image/en/binary-tree.png

There are three types of trees we will be discussing ,

### General Trees :

A tree is a finite set of nodes with one specially designated node called the root and the remaining notes are partitioned into n>=0 disjoint sets T1 and Tn where each of those sets is a tree.T1 to Tn are called the sub trees of the root

Here a is the root and other characters are each of the sets or nodes or sub trees of the root.

A simple understanding of root would be like head pointer in link list ,It holds the very initial address of the Data Structure .

A Node is an item that holds information along with address of other nodes , similar to Nodes in link list .

An Edge is an connection between two nodes , similar to *next in link list .

Now a example of This kind of Data Structure would be ,the directory / file structure of a computer .

Now the various terminologies is explained by ,https://www.tutorialride.com/data-structures/trees-in-data-structure.htm very simply.

Terminologies missing from the table , are :

1. Leaf node :If it does not have any nodes connected to it , so basically if it has no child nodes.

Depth of a tree is maximum degree of nodes in tree the root’s depth is zero, for example

* Remember the depth and level of root node is 1 ,Where as it’s degree is zero

Now a Forest can be defined as a set of n>=0 disjoint trees i.e if we remove the root , we get a forest of trees .

Now let us consider this tree then , we get forests of trees

1.Binary Trees:

A tree which has a max 2 child nodes ,along with a root node . Ex -> A is root node, also every node has a max of 2 child nodes .

Now there are various types of Binary tree:

1.Strict Binary tree : all non-leaf nodes have two nodes .

2.Full Binary tree : it has the maximum number of nodes a binary tree of depth k can have. Can also be formulated as , a tree of depth k should have 2^(k) – 1 nodes.

3.Complete Binary tree : A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

4.Almost Binary tree : if last level is partially filled

5.Skewed Binary tree : it only has diagonal branches either left or right diagonal

6.Binary Search Tree : the nodes are arranged according to value , general notation is Left-> small , parent_node->middle and right node ->big.

Application of this Trees can be seen in solving expression using expression tree ,

A general representation of binary tree

We convert a general tree into binary tree , as implementation of fixed sized nodes is easy .For example ,

Now let’s try programming binary tree using array’s , point for access will be

Conditions for accessing particular nodes will be ,

Our code snippet is :

```int Tree::getLeft(int index){
return 2*index+1;
}
int Tree::getRight(int index){
return 2*index+2;
}
int Tree::getParent(int index){
return (2*index-1)/2;
}
```

This is a simple code to represent items in array as if they were in Binary tree, like this

Now why is the array approach not scalable , same reasons as linked list .Which are,

1. Fixed Size
2. If it is not a complete tree then you will end up wasting space , as seen in the above image BT[5,6,7&8} are wasted .

Now due to it’s limitations with array , we will shift towards binary tree using linking ,as this will solve our array limitations .

The class node part should look like this :

It has 3 variables ,

1. data : to store information
2. left : to store the left sub part of tree
3. right : to store the right sub part of tree

Our class is going to look like ,

1.Create ():

1. Input data you want to enter
2. Allocate it’s memory , with new keyword . Node *newnode=new Node(data);
3. Check if root node is NULL or not , if it is NULL, that means tree is empty.
4. IF NULL , then root=newnode; give value of newnode to root.
5. Else , ask user for Left or Right of the Root Node. Put temp =root ,for iteration purposes
6. If Left , then check is temp->left =NULL . if yes , then put temp->left=NULL
7. Else temp=temp->left;
8. Same with right Node
```  {
cout<<"\n Enter the data :";
cin>>num;
newnode = new Node(num);
if (root==NULL)
{
root=newnode;//It was empty

}
else{

temp=root;
while (1)
{
char lorr;
cout<<"Left of Right"<<temp->data;
cin>>lorr;
if(lorr=='l'){
if (temp->left==NULL){
temp->left=newnode;
break;
}
else
temp=temp->left;//Until it finds an empty left node
}
if(lorr=='r'){
if(temp->right==NULL){
temp->right=newnode;
break;
}
else
temp=temp->right;//Until it finds an empty right node
}
}

}
cout<<"To continue press 0 , Else press anything";
cin>>k;

} while (k==0);
```

2.Traversal(): Recursively as well as Non-Recursively

There are various ways of traversing a tree

1.Recursive :

In recursive functions, it keeps on iterating until it reaches the required node by calling the same function just changing it’s passing para meter.

```void BinaryTree ::recursivepreorder(Node *currentnode)
{
if (currentnode != NULL){
cout<<currentnode->data;//D
recursivepreorder(currentnode->left);//L
recursivepreorder(currentnode->right);//R
}

}

void BinaryTree ::recursiveinorder(Node *currentnode)
{
if (currentnode != NULL){
recursiveinorder(currentnode->left);//L
cout<<currentnode->data;//D
recursiveinorder(currentnode->right);//R
}

}

void BinaryTree ::recursivepostorder(Node *currentnode)
{
if (currentnode != NULL){
recursivepostorder(currentnode->left);//L
recursivepostorder(currentnode->right);//R
cout<<currentnode->data;//D
}

}
```

2.Non-Recursive:

The algorithm we are going to use is ,

We are using inbuilt module of Stack and queue in our code, let me share the pseudo algorithm

1.In-order():

1. temp=root,for iteration purposes
2. Now push temp into stack and iterate it for temp=temp->next;
3. if stack is empty break the condition, done with empty ().
4. Now pop form stack//l
5. display node//d
6. Move temp=temp->right//r

2.Pre-order ():

1. temp=root,for iteration purposes
2. display temp ->data;//d
3. Now push temp into stack and iterate it for temp=temp->next;
4. if stack is empty break the condition, done with empty ().
5. Now pop form stack //l
6. Move temp=temp->right//r

3.Post-order():

1. Push root into Stack_One.
2. while(Stack_One is not empty)
1. Pop the node from Stack_One and push it into Stack_Two.
2. Push the left and right child nodes of popped node into Stack_One.
3. End Loop
4. Pop out all the nodes from Stack_Two and print it.

For better understanding , https://algorithms.tutorialhorizon.com/binary-tree-postorder-traversal-non-recursive-approach/

```void BinaryTree ::nonrecursivepreorder(Node *currentnode)
{
temp=root;
stack<Node *> s;
cout<<"inorder traversal";
while (1)
{
while (temp != NULL) {
cout<<temp->data ;
s.push(temp);
temp = temp->left;
}
// check if Stack is emtpy, if yes, exit from everywhere
if (s.empty()) {
return;
}
// pop the element from the stack and go right to the tree
temp = s.top();
s.pop();
temp = temp->right;
}

}

void BinaryTree ::nonrecursiveinorder(Node *currentnode)
{

temp=root;
stack<Node *> s;
cout<<"inorder traversal";
while (1)
{
while (temp!=NULL)
{
s.push(temp);
temp=temp->left;
}
if (s.empty())
{
return;//Empty tree
}
temp=s.top();
s.pop();

cout<<temp->data;
temp=temp->right;
}

}

void BinaryTree ::nonrecursivepostorder(Node *currentnode)
{
stack<Node *> s1;
stack<Node *> s2;
s1.push(currentnode);
while (s1.empty() == false) {
// take out the root and insert into second stack.
temp = s1.top();
s1.pop();
s2.push(temp);
// now we have the root, push the left and right child of root into
// the first stack.
if(temp->left!=NULL){
s1.push(temp->left);
}
if(temp->right!=NULL){
s1.push(temp->right);
}
}
//once the all node are traversed, take out the nodes from second stack and print it.
cout<<"Preorder Traversal";
while(s2.empty()==false){
cout<<s2.top();
s2.pop();
}

}
```

3.Insert() :

Same as Create, except we only take one value to input

```void BinaryTree::Insert(int number){

Node *newnode=new Node(number);
if (root==NULL)
root=newnode;
else
{
temp=root;

while(1){
char lorr;
cout<<"Left or Right "<<temp->data;
cin>>lorr;
if(lorr=='l'){
if (temp->left==NULL)
{
temp=temp->left;break;
}
else
temp=temp->left;

}
if(lorr=='r'){
if (temp->right==NULL)
{
temp=temp->right;break;
}
else
temp=temp->right;

}

}
}
}
```

4.Copy

```Node * BinaryTree :: copy(Node *root){
if(root == NULL)
return NULL;
/* create a copy of root node */
Node* newNode = new Node(root->data);
/* Recursively create clone of left and right sub tree */
newNode->left = copy(root->left);
newNode->right = copy(root->right);
/* Return root of cloned tree */
return newNode;
}

```

5.Mirror

```Node * BinaryTree :: mirror(Node *root){
if(root == NULL)
return NULL;
/* create a copy of root node */
Node* newNode = new Node(root->data);
/* Recursively create mirror of left and right sub tree */
newNode->left = mirror(root->right);
newNode->right = mirror(root->left);
/* Return root of mirror tree */
return newNode;
}
```

6.Count total Nodes:

```int BinaryTree::totalNodes(Node *root){

int count=0;
if (root!=NULL)
{
count++;
totalNodes(root->left);
totalNodes(root->right);
}
return count;
}
```

7.Count Leaf Nodes:

```int BinaryTree::leafNodes(Node * root){
int countleaf=0;
if(root==NULL)
return countleaf;
if(root->left ==NULL &&root->right ==NULL)
return ++countleaf;
leafNodes(root->left);
leafNodes(root->right);
}
```

Binary Search tree , AVL and Threaded tree in next blog , https://programmerprodigy.code.blog/2020/05/02/binary-search-tree/

GitHub code :https://github.com/kakabisht/Data-structures