Binary Tree in DataStructures in C
A Binary tree is a non-linear data structures where each node can only have two children, the left and right.
The top node of a binary tree is called the root, while its lower nodes are called leaves. The binary tree's roots and leaves are located at the top and bottom, respectively, of a hierarchical structure.
![Binary Tree in DataStructures in C](https://static.tutorialandexample.com/c/binary-tree-in-datastructures-in-c1.png)
The top node of the binary tree is known as the root, and every other node in the tree is either a parent, a left child, or a right child.
- This gives the binary tree the appearance of an upside-down tree. Any node's left-left and right children may be referenced and pointed to, and these references are commonly denoted by "left" and "right" pointers.
- A node may have a maximum of two offspring per the binary tree.
- Here, the binary term itself denotes "two," therefore each node might have 0,1 or 2 children.
Characteristics of Binary Tree:
The top node of the binary tree is known as the root, and every other node in the tree is either a parent, a left child, or a right child. This gives the binary tree the appearance of an upside-down tree. Any node's left-left and right children may be referenced or pointed to; these references are commonly denoted by "left" and "right" pointers.
![Binary Tree in DataStructures in C](https://static.tutorialandexample.com/c/binary-tree-in-datastructures-in-c2.png)
- Root: The root of the tree is its highest node. It is not the child of anyone.
- Parent: A parent node has one or more child nodes.
- Child: Nodes that are directly linked to a parent node.
- Leaf: A leaf node is a node without children, also known as a terminal node.
- Internal node: An internal node is a node that has at one child node.
- Subtree: A binary tree created from a node and its offspring.
- Height: Height is determined by counting the edges that make up the straightest path from the start node to end node. The usual way to express a tree's height is as -1.
- Depth: The node's depth is the number of nodes between a node and the root node or the length of the path leading from that node to that specific node.
- Level: The number of steps from the top/root is represented by the level in the tree. According to the tree's level system, the root node is at level 0, and as we descend, the level rises.
A binary tree has three components at each node:
- Data item
- Address of a left child
- Address of a proper child
![Binary Tree in DataStructures in C](https://static.tutorialandexample.com/c/binary-tree-in-datastructures-in-c3.png)
Properties of Binary Tree:
- The maximum number of nodes at each level of i is 2i.
- The largest path from the root node to the leaf node measures a tree's height. The tree depicted above is three stories tall.
- Therefore, the maximum number of nodes at height is 3.
- The maximum of nodes at height h is typically 2h+1 -1.
- At height h, there can only be a minimum of h+1 nodes.
- The tree's height would be at its greatest if the number of nodes were at its lowest.
- In contrast, the tree's height would be the smallest if the number of nodes was maximal.
Representation of Binary Tree:
There are two types of Representation:
- Array Representation(sequential)
- Linked Representation(Node-Based)
Array Representation(sequential):
Binary trees are kept in an array in this Representation, called array-based. Sequential memory allocation is typically used to implement the array.
![Binary Tree in DataStructures in C](https://static.tutorialandexample.com/c/binary-tree-in-datastructures-in-c4.png)
- The left child of a node at index I in the array is found at index 2i+1, and the correct child is found at index 2i+2.
- The binary tree is said to be complete when all levels are filled, except for the last level, filled from left to right.
- This format may save memory space when the tree is complete because some array elements will go unused.
- Additionally, this Representation calls for shifting elements if the tree is changed.
Node-Based Representation (Linked Structure):
In this Representation, pointers and nodes represent a binary tree. Each node has data and pointers (or NULL if none exist) to its left and right children.
![Binary Tree in DataStructures in C](https://static.tutorialandexample.com/c/binary-tree-in-datastructures-in-c5.png)
- A pointer to the topmost node serves as the tree's Representation of the root.
- This form is more adaptable and practical for dynamic binary trees because it allows memory only for the necessary nodes.
- It enables simple tree editing and navigation. This node-based model is used by most binary tree implementations, including the one I gave before.
Binary Trees are required.
- Even with massive data sets, searching becomes simple and quick with a binary search tree.
- There is no restriction on the number of nodes in trees. So, unlike an array, a tree can be formed and extended in size as the user needs.
- Hierarchical data can be stored in the database.
- The database can hold hierarchical data.
- Additionally, classification and decision-making can be done using a binary tree.
Types of Binary Trees:
Full Binary/Proper/Strict:
A strict binary tree is another name for the full binary tree. If every node has 0 or 2 child, the tree can be considered a complete binary tree. The phrase "full binary tree" can also apply to a tree where every node, except the leaf nodes, must have two offspring.
![Binary Tree in DataStructures in C](https://static.tutorialandexample.com/c/binary-tree-in-datastructures-in-c6.png)
Properties of Full Binary tree:
- As can be seen from the observation, it is a complete binary tree because each node has either zero or two offspring.
- The Features of The Full Binary Tree. The number of leaf nodes is one more than the number of internal nodes.
- The most nodes possible are 2h+1-1, which is the same as the number of nodes in the binary tree.
- There must be at least 2*h-1 nodes in the entire binary tree.
- The tree is at least log2(n+1)-1 tall.
- The binary tree has a minimum height of log2(n+1) - 1.
The following formula can be used to calculate the entire binary tree's maximum height:
- n= 2*h – 1
- n+1 = 2*h
- h = n+1/2
Complete Binary Tree:
Except for the top level, every node in the whole binary tree is filled. All nodes must be as far to the left in the final level as possible. A whole binary tree should be constructed by adding the nodes from the left.
![Binary Tree in DataStructures in C](https://static.tutorialandexample.com/c/binary-tree-in-datastructures-in-c7.png)
Properties of Complete Binary Tree:
- The whole binary tree can have a maximum of 2h+1 - 1 nodes.
- There must be at least 2h nodes in a complete binary tree.
- log2(n+1) - 1 is the minimal height of a complete binary tree.
Perfect Binary Tree
If every leaf node is at the same level and every interior node has two offspring, the tree is a perfect binary tree.
![Binary Tree in DataStructures in C](https://static.tutorialandexample.com/c/binary-tree-in-datastructures-in-c8.png)
Note: The converse is not true since all whole and complete binary trees are perfect binary trees, but all complete and total binary trees are perfect.
Degenerate Binary Tree
A degenerate binary tree has just one offspring for each internal node. Where there is a right and left skewed trees.
Right-skewed tree:
A binary tree of the right-skewed kind has no left children and only one right child for each node. The tree, often referred to as a "right-leaning" or "right-heavy" tree, grows towards the right as it lower
![Binary Tree in DataStructures in C](https://static.tutorialandexample.com/c/binary-tree-in-datastructures-in-c9.png)
Left-skewed tree:
A binary tree of the left-skewed kind has no right children and only left children for each node. A "left-leaning" or "left-heavy" tree is one that leans more to the left as it grows downward.
![Binary Tree in DataStructures in C](https://static.tutorialandexample.com/c/binary-tree-in-datastructures-in-c10.png)
Balanced Binary Tree
When the highest difference between the left and right trees is 1, the binary tree is said to be balanced. AVL and Red-Black trees are two examples of balanced binary trees.
![Binary Tree in DataStructures in C](https://static.tutorialandexample.com/c/binary-tree-in-datastructures-in-c11.png)
- It ensures efficient operations even with dynamic insertions and deletions by using rotations to preserve balance.
- Another self-balancing binary search tree is the red-black tree. Utilizing color labels on the nodes adheres to specific characteristics, such as guaranteeing balanced routes from the root to the leaves.
- Red-black trees are popular in many applications and offer effective operations.
Binary Tree Implementation:
A binary tree is implemented using pointers. The root pointer represents the very first node of the tree. Before developing a binary tree, we must first construct the node.
struct node{
int data;
struct node* left;
struct node* right;
};
Example:
#include<stdio.h>
#include<stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
struct Node* createNode(int data) {
struct Node* newNode =(struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("memory allocation fail!\n");
return NULL;
}
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
void inorder traversal(struct Node* root) {
if (root == NULL)
return;
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
int count nodes(struct Node* root) {
if (root == NULL)
return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
int main() {
struct Node* root = createNode(6);
root->left = createNode(5);
root->right = createNode(4);
root->left->left = createNode(2);
root->left->right = createNode(9);
printf("Nodes of tree: ");
inorderTraversal(root);
printf("\n");
int nodeCount = countNodes(root);
printf("Number of nodes in the tree: %d\n", nodeCount);
return 0;
}
Output:
![Binary Tree in DataStructures in C](https://static.tutorialandexample.com/c/binary-tree-in-datastructures-in-c12.png)
The root node of the binary tree, which is constructed, has a value of 6. The root's left child is five, and the correct child is four. Two is the left child of five, while nine is the right child.
- To display the tree's nodes in inorder traversal order, the inorderTraversal() function is used.
- The countNodes() function calculates the total number of nodes in the tree. The results of the count are printed on the console.
The program will output the tree's nodes in the order of in-order Traversal Traversalexecute and the total number of nodes in the tree.
Binary Tree Traversals
- Preorder Traversal
- In order Traversal
- Traversal Traversal
Preorder Traversal:
In the preorder traversal, the current node is visited first, followed by the left subtree and then the right subtree. Because the current node is visited before its offspring, it is called a "preorder" system.
Its Visits the current node before going to any nodes inside the left or right subtrees with the preorder Traversal Traversalleft-right).
- The Traversal Traversalnstance is root - left child - right child. According to this, the root node is traversed first, then its left child, and finally its right child.
void preorder traversal(struct Node* root) {
if (root == NULL)
return;
printf("%d -> ", root->data);
preorder traversal(root->left);
preorder traversal(root->right);
}
The binary tree is traversed by the function in a preorder manner, with the current node being visited first, then the left subtree, and finally, the right subtree. The function recursively calls itself on each node's left and right children.
Inorder Traversal:
In the inorder traversal, the current node is visited first, followed by the left subtree, and then the right subtree. When the tree depicts components in a meaningful order, the nodes are visited in ascending order.
- The traversal order, in this case, is left-to-right-child-root. The left child, its root node, and the right child are traversed.
void inorder traversal(struct Node* root) {
if (root == NULL)
return;
inorderTraversal(root->left);
printf("%d -> ", root->data);
inorderTraversal(root->right);
}
The function executes an orderly traverse of the binary tree, visiting the left, left, current node, and right subtree in that order. The function recursively calls itself on each node's left and right children.
Post order Traversal:
The left subtree is the first to be seen during a postorder traversal, followed by the right subtree and the current node. The reason it is named "postorder" is because the children of the current node are visited first.
Go to the current node after viewing each node in the left and right subtrees. In this instance, the traversal Right child - left child - root.
- This shows that the right child and its root node were investigated after the left child.
void postorderTraversal(struct Node* root) {
if (root == NULL)
return;
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d -> ", root->data);
}
The function runs a postorder traversal of the binary tree, visiting the left, correct, and current nodes in that order. The function recursively calls itself on each node's left and right children.
Example:
#include <stdio.h>
#include <stdlib.h>
struct node {
int item;
struct node* left;
struct node* right;
};
//In order traversal
void inorder traversal(struct node* root) {
if (root == NULL) return;
inorder traversal(root->left);
printf("%d ", root->item);
inorder traversal(root->right);
}
//Preorder Traversal
void preorder traversal(struct node* root) {
if (root == NULL) return;
printf("%d ", root->item);
preorder traversal(root->left);
preorder traversal(root->right);
}
// Postorder traversal
void postorderTraversal(struct node* root) {
if (root == NULL) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->item);
}
// Create a new Node
struct node* create(int value) {
struct node* newNode = malloc(sizeof(struct node));
newNode->item = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Insert on the left of the node
struct node* insert left(struct node* root, int value) {
if (root == NULL) return NULL;
root->left = create(value);
return root->left;
}
// Insert on the right of the node
struct node* insert right(struct node* root, int value) {
if (root == NULL) return NULL;
root->right = create(value);
return root->right;
}
int main() {
struct node* root = create(99);
struct node* leftChild = insertLeft(root, 44);
struct node* rightChild = insertRight(root, 77);
insertLeft(leftChild, 22);
insertRight(leftChild, 52);
insertLeft(rightChild, 88);
insertRight(rightChild, 64);
printf("Traversal of the inserted binary tree \n");
printf("Inorder traversal: ");
inorderTraversal(root);
printf("\nPreorder traversal: ");
preorderTraversal(root);
printf("\nPostorder traversal: ");
postorderTraversal(root);
return 0;
}
Output:
![Binary Tree in DataStructures in C](https://static.tutorialandexample.com/c/binary-tree-in-datastructures-in-c12.png)
Before inserting the left or right child, the insertLeft() and insertRight() functions now make a check to see if the root node is NULL. This prevents potential problems when using a NULL node to call these functions.
![Binary Tree in DataStructures in C](https://static.tutorialandexample.com/c/binary-tree-in-datastructures-in-c13.png)
Binary Tree Operations
Create a Node
Allocate memory for a struct Node, give it a data value, and set its left and right pointers to NULL to construct a new node. Here is a createNode() function example.
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
return NULL;
}
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
Insert a Node:
Finding the right spot in the tree and adding the new node as a child of an existing node are necessary steps for inserting a node. The insertion procedure is determined by the binary tree's intended ordering property, for example, the binary search tree.
struct Node* insertNode(struct Node* root, int data) {
if (root == NULL) {
return createNode(data);
}
if (data < root->data) {
root->left = insertNode(root->left, data);
} else if (data > root->data) {
root->right = insertNode(root->right, data);
}
return root;
}
Delete a Node:
When deleting a node, find the node to delete and adjust the tree structure as necessary. Whether a node has one child, two children, or is a leaf node, the deletion process varies depending on the circumstance
struct Node* delete node(struct Node* root, int data) {
if (root == NULL) {
return root;
}
if (data < root->data) {
root->left = delete node(root->left, data);
} else if (data > root->data) {
root->right = delete node(root->right, data);
} else {
if (root->left == NULL) {
struct Node* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct Node* temp = root->left;
free(root);
return temp;
}
struct Node* minValueNode = findMinValueNode(root->right);
root->data = minValueNode->data;
root->right = deleteNode(root->right, minValueNode->data);
}
return root;
}
Search a Node:
To find a node, navigate the binary tree until you reach the node with the specified value. Recursive or iterative algorithms like depth-first search (DFS) or breadth-first search (BFS) are frequently used to carry out this procedure.
struct Node* search node(struct Node* root, int data) {
if (root == NULL || root->data == data) {
return root;
}
if (data < root->data) {
return searchNode(root->left, data);
} else {
return searchNode(root->right, data);
}
}
Is empty:
Determining whether a binary tree is empty or devoid of nodes is known as "check if the tree is empty." It can be carried out by determining whether the root pointer is NULL.
Tree’s Height: The total number of edges between the root and a leaf node determines the height of a binary tree. This algorithm iteratively calculates the height of the tree.
int get eight(struct Node* root) {
if (root == NULL)
return -1; //height of an empty tree is -1
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
return 1 + max(leftHeight, rightHeight);
}
Applications of Binary Tree:
Binary search trees (BST): BST Known as binary search trees, these trees have the ordering property of binary trees.
- They are frequently employed for effective insertion, deletion, and searching procedures. For effective data retrieval, BSTs are used in data structures like symbol tables and balanced BSTs (e.g., AVL trees, Red-Black trees).
Expression Trees: Binary trees, where the internal nodesand operators, the leaf nodes are operands, can represent arithmetic expressions.
- Compilers, interpreters, and mathematical software employ expression trees to evaluate and work with arithmetic expressions.
Huffman Coding: Based on a character's frequency of occurrence, Huffman Coding uses binary trees to give characters variable-length codes.
- Data storage optimization techniques and file compression algorithms both use Huffman trees.
Binary Heaps: Complete binary trees that meet the heap property are known as binary heaps.
- They are utilized in heap-based sorting techniques like heap sort and priority queues. Scheduling, graph algorithms (like the Dijkstra method), and data stream processing all use binary heaps.
Decision tree: Binary trees used for categorization or decision-making activities are called decision trees.
- Each internal node represents a decision or attribute, whereas each leaf node represents an outcome or class label.
- Random forests and ID3 (Iterative Dichotomiser 3) are machine-learning techniques that use decision trees.
Syntax Trees: In computer languages, syntax trees, commonly called parse trees, depict the structure of phrases or expressions.
- They are utilized in compilers, interpreters, and language processing tools for syntactic analysis and semantic interpretation.
Game Tree: Binary trees can model game scenarios and tactics. In artificial intelligence techniques like alpha-beta pruning and minimax search, game trees are used to discover the best moves in games like chess, tic-tac-toe, and game-playing agents.