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 :
- 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,
- Fixed Size
- 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 ,
- data : to store information
- left : to store the left sub part of tree
- right : to store the right sub part of tree
Our class is going to look like ,
1.Create ():
- Input data you want to enter
- Allocate it’s memory , with new keyword . Node *newnode=new Node(data);
- Check if root node is NULL or not , if it is NULL, that means tree is empty.
- IF NULL , then root=newnode; give value of newnode to root.
- Else , ask user for Left or Right of the Root Node. Put temp =root ,for iteration purposes
- If Left , then check is temp->left =NULL . if yes , then put temp->left=NULL
- Else temp=temp->left;
- 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():
- temp=root,for iteration purposes
- Now push temp into stack and iterate it for temp=temp->next;
- if stack is empty break the condition, done with empty ().
- Now pop form stack//l
- display node//d
- Move temp=temp->right//r
2.Pre-order ():
- temp=root,for iteration purposes
- display temp ->data;//d
- Now push temp into stack and iterate it for temp=temp->next;
- if stack is empty break the condition, done with empty ().
- Now pop form stack //l
- Move temp=temp->right//r
3.Post-order():
- Push root into Stack_One.
- while(Stack_One is not empty)
- Pop the node from Stack_One and push it into Stack_Two.
- Push the left and right child nodes of popped node into Stack_One.
- End Loop
- 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
Programmer Prodigy 
2 thoughts on “Trees to Binary Trees”