Binary Trees

BINARY TREES

Pre-requiste : Recursion

Why do we need trees when we have linked list?

Because traversal in a linked list needs visiting all the nodes, which would take a billion of time for a billion nodes, but just a few steps on a binary tree with its unique O(log n) time complexity.

So, binary trees are more efficient than linked lists.

So, how does searching in a binary tree takes O(log n), because nodes might have been placed randomly anywhere.

For that purpose, we use a special tree, we say, Binary Search Trees, where the smaller value is placed at left side, and greater value is placed at right side.

A Binary search tree has Ordered Storage,

And also very Cost efficient.

For example, suppose we had to create a binary search tree with nodes, 10, 5, 20, 5, 7, and 18. Then, we’d take the first node retrieved as the root node, further extending to its children. Now, the next element would be either less or greater, and according we insert it with the root tree.

For inserting 7, we compare with root, its less, but it already has a left child, so we traverse deeper, and assume our next root node to be 5, then we do the same comparison, and place it on the right side as 7 is greater. Similarly, we do the same for inserting 18.

Unbalanced Tree

However, in cases like above, our tree may get unbalanced, which might not fulfill our purpose of using the tree data structure, to efficiently store and retrieve data, taking ultimately O(n) time.

In such a case, we find out when a tree gets unbalanced, and we do rotations and transformations to make kind of a balanced tree.

We find out such a case, using the height difference between its left and right leaf nodes. When its greater than 1. Boom ! Unbalanced.

When these balances are checked in its implementation, that tree is known as a Self Balancing Tree.

Where is binary tree used?

File Systems, where binaries are used to represent file systems, you know your folders and stuff like that you care about. Every single node represents a folder directory, and every single leaf node represents a file, and they together have a beautiful parent-child relationship which blends well in this structure.

Databases, Binaries are used to store and retrieve key and value pairs effectively. A special kind of tree for this is called B- Trees and B+ Trees.

Network Routing, It’s used in path-finding algorithms and finding the right route effectively.

Compression of files, using Huffman coding algorithms and others.

Decision Trees, and various other machine learning algorithms.

Advanced Data Structures, such as AVL Trees, Red-Black Trees, Segment Trees, Graphs, Heaps and Tries.

Tree is actually a type of graph that is directed and acyclic in nature.

How does the Binary Tree Structure looks like?

Node{

int value [ It stores the value at that node ]

Node* left [ It stores the address of left node ]

Node* right [ it stores the address of right node ]

}

The Structure of a Binary tree is such that the first inserted node in the tree is considered as the root of the tree, following that it can store the address of a left child node, and a right child node, and storing a value with it, it has the ability to extend its branches.

The child nodes been created from the same structure also has the ability to extend itself, storing a left child node, and a right child node.

However, in the above diagram, the child node does not have any further nodes. So, its left and right node addresses will point to a null value. Otherwise, trying to access a null node will give us, what is popularly known as, Segmentation Fault.

Internally, we’re using Linked List as its implementation of this binary tree. The linked list has two pointers, left and right.

If two nodes have the same parent, they are called Siblings. Here above also Siblings are said to have a common node.

Properties of Binary Trees

1. Size = Total number of nodes
2. Height = Maximum number of edges between two nodes
3. Level = Height of root - Height of Node
4. Pointers that connects nodes together are called edges
5. Nodes having a common parent are called siblings
6. Nodes having no further children are called leaf nodes
7. Nodes from where current node extends are called ancestors

For example, the size of above tree is 9. The height of the above tree is 4. The level is calculated for each node. The level for node 8 suppose is, height of root (4) - height of node (3), which is 1.

The nodes 3 and 4 are siblings as they have a common parent. The nodes having no further children such as 14, 15, ,4, 11 are leaf nodes.

Here, 4 has been extended from 7, 8, 5. They are all ancestors.

Types of Binary Trees

1. Complete Binary Tree ~

[ Nodes in all levels have two children apart from the last level ]

[ Last level has two children from left to right ]

1. Full Binary Tree [Strict Binary Tree] ~

[ Each node has either 0 children or 2 children ]

Full Binary Trees are used in compression, segment trees.

1. Perfect Binary Tree ~

[ All levels are filled completely ]

1. Height Balanced Tree ~

[ AVL Trees, Red-Black Trees ]

AVL Trees and Red-Black Trees have the power to balance themselves through rotations. Hence, they are height balanced because their average height is always O(log n)

1. Skewed Binary Tree ~

[ Every node has one child ]

1. Ordered Binary Tree

[ Every node has some property to order it ]

For example, Binary Search Tree has ordering property such that If value < root then it goes to left node or if value >= root then it goes to right node, similar to how binary search finds the middle and either goes left or right depending on comparison.

In-depth Properties of Binary Trees

1. Total Nodes in Perfect Binary Tree = 2^(Height + 1) - 1

1. Leaf Nodes in Perfect Binary Tree = 2^(Height)

1. Minimum Level of Binary Tree = log(Number of Nodes + 1)

1. No. of leaf nodes in Strict Binary Tree = Internal Nodes + 1

Binary Trees Representation

1. Using Linked Lists
2. Sequential Using Arrays

For Binary Trees, Linked Lists are preferred, because if arrays are used, half of the array space will not be used efficiently as the leaf node contains null values.

However, there are some special binary trees such as priority queues where arrays are preferred, because we have to sequentially access the nodes. In priority queues, the top node always contains the node that is at priority and hence it is always first to be popped out.

We generally store a binary tree like a binary search tree, even if a binary tree does not strictly follow the ordering like a binary search tree, it’s still preferred to implement it this way, else there’d be no particular ordering on the basis of where to insert or delete.

Binary Tree Implementation Using Linked Lists

#include <stdio.h>
#include <stdlib.h>


// basic structure of a node having a left and a right pointer to store the address of respective child nodes

typedefstructNode{
int value;
structNode* left;
structNode* right;
} NODE;

// initializing a node means handling a new node null pointers properly to avoid segmentation fault

voidinitialize(int e, NODE* ROOT){
ROOT->left = NULL;
ROOT->right = NULL;
ROOT->value = e;
}

// this function is used to insert a value in the binary tree, it works on the principle of recursion.

// first, we’re doing the comparison of the value that we are going to insert with the value of the current node, if the value is less than the value at node, we go to the left subtree by calling the function again with its left child. Similarly, we do the same for right subtree if the value is greater than node value.

// If the node has no further children, it will encounter the first base condition, when a recursive call has been made for the node that stores a NULL value in its left and right pointers. This base condition of recursion, stops further infinite recursive calling and returns a void to its previous caller.

// The previous caller is the parent node that has called this recursive function on its left or right child. Once caller gets back the control, it executes the function further, checking whether the child of the caller was actually NULL. If it is NULL, we dynamically create the node memory, and make the node point to this new address. We also initialize the new node with null values to handle the null pointer exceptions.

// The interesting thing is that if the recursive calling hits the base case when node passed into the insert function is null, then why do we check whether it is null before creating the new node. Because on actually getting back to the caller, only the first parent caller will have its child nodes as null, but when it goes back further to its further parent caller, till the point of reaching the root node again, to complete the functions, then in all those cases, the children of those nodes will not be null.

voidinsert_binary_tree(int e, NODE* node){
if(node == NULL){
return;
}
if(e < node->value){
insert_binary_tree(e, node->left);
if(node->left == NULL){
NODE* new = (NODE*) malloc(sizeof(NODE));
new->value = e;
node->left = new;
initialize(e, new);
}
} else {
insert_binary_tree(e, node->right);
if(node->right == NULL){
NODE* new = (NODE*) malloc(sizeof(NODE));
new->value = e;
node->right = new;
initialize(e, new);
}
}
}

// This function has been created to find the inorder successor for the node that we have to delete but because it has 2 children, we have to replace it with its nearest greater element. If we do not replace it and directly delete the node having further children, then it will be impossible to get the address of its children and they will be lost forever.

intfind_inorder_Successor(NODE* node){
if(node == NULL){
return-1;
}
find_inorder_Successor(node->left);
return node->value;

}

// When we think of deleting a binary tree, three cases do arise, first is that it may have no children, then it may have a single child, either on the left side or on the right side, then it may have two children.

// firstly, we find that node that we have to delete, otherwise what would we delete? If we don’t find it, it’s obviously not in the tree, and the value is not found.

// But how do we find it? Using comparisons, if it’s value is less, it goes to its left child, if it’s value is more, it goes to its right child, otherwise if it’s value is same, we found it !

// In this function, we’re also seeing that if its children actually exist and are not null, and the value of node is also not same, then it’s obvious that we have to traverse deeper into the tree, we hit up a recursion to find the thief we’re looking for !

// If we have not found the element, then we have obviously at a leaf node, where its children are null, and the value is not same, then we return not found.

// Else if we do have the value same as the node, then it can either have no child, which is pretty simple, we return a NULL address to the parent caller that called upon its child node, or it can have one child, but to be careful as the one child can either be on the left side or on the right side, which has to be handled separately. For one child, we return the address of the next node to the parent caller.

// When we get the node to be deleted with two children following it, we basically have to find the nearest greater element to replace it with, a nearest greater element is always greater than deleted node value, which means its replacement will always be in the right subtree. However in the right subtree we've to find the least value. Hence, the left-most node in the right subtree will be its replacement.

NODE* delete_binary_tree(int e, NODE* node){
if(node == NULL){
returnNULL;
}

if(node->left != NULL && e < node->value){
node->left = delete_binary_tree(e, node->left);
} elseif(node->right != NULL && e > node->value){
node->right = delete_binary_tree(e, node->right);
} else {

if(node->left == NULL && e < node->value ||
node->right == NULL && e > node->value){
printf("Element %d not found", e);
return node;

// no child
} elseif(node->left == NULL && node->right == NULL && node->value == e){
free(node);
returnNULL;

// one left child
} elseif(node->left != NULL && node->right == NULL && node->value == e){
NODE* temp = node->left;
free(node);
return temp;

// one right child
} elseif(node->left == NULL && node->right != NULL && node->value == e){
NODE* temp = node->right;
free(node);
return temp;

// two child
} elseif(node->left != NULL && node->right != NULL && node->value == e){
int temp = find_inorder_Successor(node->right);
delete_binary_tree(temp, node->right);
node->value = temp;
return node;
}

}
return node;
}

// preorder means visiting the node for the first time, and printing it at that time itself.

voidpreorder_traversal(NODE* node){
if(node == NULL){
return;
}
printf(" %d ", node->value);
preorder_traversal(node->left);
preorder_traversal(node->right);
}

// inorder means visiting the node for the second time, which happens to be the case, when the function returns something and goes back to the parent caller. It’s like reaching for the left node, but because it was null, it came back from where it came from.

voidinorder_traversal(NODE* node){

if(node == NULL){

return;

}

inorder_traversal(node->left);

printf(" %d ", node->value);

inorder_traversal(node->right);

}

// postorder means visiting the node for the third time, which happens to be the case, when you have also visied the right child, and the function scope goes back to the parent caller, for the second time, because for the first time, it was for the left node.

voidpostorder_traversal(NODE* node){
if(node == NULL){
return;
}
postorder_traversal(node->left);
postorder_traversal(node->right);
printf(" %d ", node->value);

}
intmain(){

NODE ROOT;
initialize(10, &ROOT);

insert_binary_tree(06, &ROOT);
insert_binary_tree(30, &ROOT);

preorder_traversal(&ROOT);
printf(" preorder \n\n");

inorder_traversal(&ROOT);
printf(" inorder \n\n");

postorder_traversal(&ROOT);
printf(" postorder \n\n");

delete_binary_tree(30, &ROOT);

insert_binary_tree(15, &ROOT);
insert_binary_tree(2, &ROOT);

preorder_traversal(&ROOT);
printf(" preorder \n\n");

inorder_traversal(&ROOT);
printf(" inorder \n\n");

postorder_traversal(&ROOT);
printf(" postorder \n\n");
return0;
}

Traversal Methods

1. Preorder

1. Inorder

In binary search trees, inorder traversal gives us sorted values.

1. Postorder

For example

Preorder

Inorder

Postorder

Find duplicate nums in a given list using Binary Tree

#include <stdio.h>
#include <stdlib.h>
typedefstructNode{
int value;
structNode* left;
structNode* right;
} NODE;
#define MAX 100
staticint counter = 0;
staticint duplicates[MAX];
voidinitialize(int e, NODE* ROOT){
ROOT->left = NULL;
ROOT->right = NULL;
ROOT->value = e;
}
voidinsert_binary_tree(int e, NODE* node){
if(node == NULL){
return;
}
if(e < node->value){
insert_binary_tree(e, node->left);
if(node->left == NULL){
NODE* new = (NODE*) malloc(sizeof(NODE));
new->value = e;
node->left = new;
initialize(e, new);
}
} elseif(e > node->value){
insert_binary_tree(e, node->right);
if(node->right == NULL){
NODE* new = (NODE*) malloc(sizeof(NODE));
new->value = e;
node->right = new;
initialize(e, new);
}
} else { // duplicate found [e == node->value]
int flag = 1;
for(int i = 0; i < counter; i++){
if(duplicates[i] == e){
flag = 0; // avoids repeated values of duplicates
}
}
if(flag){
duplicates[counter++] = e;
}
}
}
voidprintlist(int arr[], int e){
for(int i = 0; i < e; i++){
printf("%d ", arr[i]);
}
}
intmain(){
int e, scan;
printf("\n\n");

printf("Enter the number of elements in the list: ");
scanf("%d", &e);

int arr[e];

NODE ROOT;

for(int i = 0; i < e; i++){
printf("Enter a number: ");
scanf("%d", &scan);
arr[i] = scan;
}
printf("\n\n");

printlist(arr, e);
printf(" original list \n\n");

for(int i = 0; i < e; i++){
if(i == 0){
initialize(arr[i], &ROOT);
} else {
insert_binary_tree(arr[i], &ROOT);
}
}

for(int i = 0; i < counter; i++){
printf("%d ", duplicates[i]);
}
printf(" duplicates found \n\n");

return0;
}

Sort a list of numbers using Binary Search Trees
#include <stdio.h>
#include <stdlib.h>
typedefstructNode{
int value;
structNode* left;
structNode* right;
} NODE;
staticint counter = 0;
voidinitialize(int e, NODE* ROOT){
ROOT->left = NULL;
ROOT->right = NULL;
ROOT->value = e;
}
voidinsert_binary_tree(int e, NODE* node){
if(node == NULL){
return;
}
if(e < node->value){
insert_binary_tree(e, node->left);
if(node->left == NULL){
NODE* new = (NODE*) malloc(sizeof(NODE));
new->value = e;
node->left = new;
initialize(e, new);
}
} else {
insert_binary_tree(e, node->right);
if(node->right == NULL){
NODE* new = (NODE*) malloc(sizeof(NODE));
new->value = e;
node->right = new;
initialize(e, new);
}
}
}
voidinorder_traversal(NODE* node, int arr[]){
if(node == NULL){
return;
}
inorder_traversal(node->left, arr);
arr[counter++] = node->value;
inorder_traversal(node->right, arr);
}
voidprintlist(int arr[], int e){
for(int i = 0; i < e; i++){
printf("%d ", arr[i]);
}
}
intmain(){
int e, scan;

printf("Enter the number of elements in the list: ");
scanf("%d", &e);

int arr[e];

NODE ROOT;

for(int i = 0; i < e; i++){
printf("Enter a number: ");
scanf("%d", &scan);
arr[i] = scan;
}
printf("\n\n");

printlist(arr, e);
printf(" original list \n\n");

for(int i = 0; i < e; i++){
if(i == 0){
initialize(arr[i], &ROOT);
} else {
insert_binary_tree(arr[i], &ROOT);
}
}

inorder_traversal(&ROOT, arr);

printlist(arr, e);
printf(" sorted list \n\n");

return0;
}



Implement Threaded Binary Trees
#include <stdio.h>
#include <stdlib.h>
typedefstructNode{
int value;
int rthread;
int lthread;
structNode* left;
structNode* right;
} NODE;
static NODE* PREV = NULL;
// used for finding inorder predessor

staticint visited = 0;
// used for finding inorder successor
voidinitialize(int e, NODE* ROOT){
ROOT->left = NULL;
ROOT->right = NULL;
ROOT->value = e;
ROOT->rthread = 0;
ROOT->lthread = 0;
}
voidinsert_binary_tree(int e, NODE* node){
if(node == NULL){
return;
}
if(e < node->value){
insert_binary_tree(e, node->left);
if(node->left == NULL){
NODE* new = (NODE*) malloc(sizeof(NODE));
initialize(e, new);
node->left = new;
}
} else {
insert_binary_tree(e, node->right);
if(node->right == NULL){
NODE* new = (NODE*) malloc(sizeof(NODE));
initialize(e, new);
node->right = new;
}
}
}
NODE* pre_inorder(int e, NODE* node){
if(node == NULL){
returnNULL;
}
pre_inorder(e, node->left);
if(node->value == e){
return PREV;
}
PREV = node;
pre_inorder(e, node->right);

return node;
}
NODE* post_inorder(int e, NODE* node){
if(node == NULL){
returnNULL;
}
post_inorder(e, node->left);
if(visited == 1){
visited = 0;
return node;
}
if(node->value == e){
visited = 1;
}

post_inorder(e, node->right);

return node;
}
voidmake_threads(NODE* node, NODE* root){
if(node == NULL){
return;
}
make_threads(node->left, root);

if(node->left == NULL){
PREV = NULL;
node->left = pre_inorder(node->value, root);
if (node->left == root) {
node->left = NULL;
}
node->lthread = 1;
}

make_threads(node->right, root);

if(node->right == NULL){
node->right = post_inorder(node->value, root);
if (node->right == root) {
node->right = NULL;
}
node->rthread = 1;

}
}
voidright_threaded_inorder(NODE* node) {
if (node == NULL) return;
right_threaded_inorder(node->left);

if (node->rthread == 1) {
printf("(Thread→%d)", node->value);
}
right_threaded_inorder(node->right);
}
voidleft_threaded_inorder(NODE* node) {
if (node == NULL) return;
left_threaded_inorder(node->left);

if (node->lthread == 1) {
printf("(Thread→%d)", node->value);
}
left_threaded_inorder(node->right);
}
intmain(){
int e, scan;
printf("\n\n");

printf("Enter the number of elements in the list: ");
scanf("%d", &e);

NODE ROOT;
for(int i = 0; i < e; i++){
printf("Enter a number: ");
scanf("%d", &scan);
if(i == 0){
initialize(scan, &ROOT);
} else {
insert_binary_tree(scan, &ROOT);
}
}

make_threads(&ROOT, &ROOT);

right_threaded_inorder(&ROOT);
printf(" Right threaded nodes");

printf("\n\n");

left_threaded_inorder(&ROOT);
printf(" Left threaded nodes");

return0;
}

=

In our implementation, the left-most null and right-most null pointers are also utlizied unlike the above diagram to point to the root node, as the intention of having a threaded binary tree is to utilize the null pointers, because there are ( number of nodes + 1 ) null nodes in a binary tree.