This blog post will give you an overview of the tree data structure in C programming language, types of tree data structure, and tree traversal techniques on a tree.
Introduction of Tree Data Structure
A tree is a hierarchical data structure (top to bottom and left to right) which consists of nodes and edges. Nodes are where we store all of our data. The data can be anything it can be integers, strings, characters, etc. The starting node or the first node in a tree is called a root node. And the nodes which don’t have any children are called the leaf node. The path which connects two nodes is called an edge.
Every node in a tree can have multiple children’s and based on the number of children’s a tree have we give that tree a unique name. Example: If every node in a tree has two children then that tree will be called as a binary tree, if every node in a tree has three children’s then it is called as a ternary tree and so on.
Below is a diagram which illustrates a binary tree.
To construct a tree, we can use linked lists.
There are some concepts in trees one is called traversing and another one is searching. Don’t get confused between traversing and searching they both are two different things. Traversing means visiting each and every node in a tree at least once. In searching, we search for a particular node in a tree and after finding that element we stop.
Traversing a tree data structure
There are 3 tree traversal techniques. And in all those techniques, the order in which we traverse the root node changes. But when it comes to the left child and right child of a tree we traverse them in the same sequence i.e we traverse the left child first and then the right child in every traversal technique.
Preorder Traversal (Root – Left – Right)
In Preorder, the root node is printed first and then the left and right child. Therefore it is called preorder traversal.
struct node{
char data;
struct node *left, *right;
}
void Preorder(struct node *t){
if(t != NULL){
printf("%c", t->data);
Preorder(t->left);
Preorder(t->right);
}
}
- Inorder Traversal (Left – Root – Right)
struct node{
char data;
struct node *left, *right;
}
void Inorder(struct node *t){
if(t != NULL){
Inorder(t->left);
printf("%c", t->data);
Inorder(t->right);
}
}
Postorder Traversal (Left – Right – Root)
In Postorder, the left and right child are printed first and then the root node. Therefore it is called Postorder traversal.
struct node{
char data;
struct node *left, *right;
}
void Postorder(struct node *t){
if(t != NULL){
Postorder(t->left);
Postorder(t->right);
printf("%c", t->data);
}
}
All the above 3 tree traversal techniques will take the same time complexity and space complexity of O(n).
Types of trees
Binary Tree
Binary tree is a tree in which every node consist of either two children’s or zero children’s. Except the leaf node all the other nodes will have two children’s.
Binary Search Tree
As the name suggests it’s a binary tree (having two or zero children) but in this case here we have a condition and that is the elements present in the left subtree must be lesser than the value of the root element and the elements which are present at the right subtree must be greater than the value of the root element. This condition is applicable to each and every node in the binary search tree because each node will have either a left subtree or a right subtree or both.
Balanced Binary Search Tree (AVL Tree)
Now to check if the tree is balanced or not there is a concept called Balanced Factor (BF). The Balanced Factor for a particular node in an AVL tree can be either -1, 0, or 1 (which means the node is balanced). If the balanced factor of the node is other than these numbers say 2 or -2 then we have to balance that particular node. Below is the formula to find the balanced factor.
Balanced Factor (BF) = Height of Left Subtree (LST) – Height of Right Subtree (RST)
Every time we insert a node into the balanced binary search tree (AVL tree) we have to check whether we have any kind of imbalance in a tree or not. If there is any imbalance then we have to balance it using the below imbalance techniques.
There are 4 types of imbalances possible in AVL tree.
a. Left-Left Imbalance (LL imbalance)
From the below figure we can see that the tree has LL imbalance. So we have to rotate the tree in a clockwise direction to make it balanced.
b. Right-Right Imbalance (RR imbalance)
If we have RR imbalance in a tree then we have to rotate the tree in a anticlockwise direction to make it balanced.
c. Left-Right Imbalance (LR imbalance)
If we have an LR imbalance in a tree then we have to perform 2 rotations. First rotate anticlockwise (RAC) and second rotate clockwise (RCW).
d. Right-Left Imbalance (RL imbalance)
If we have an RL imbalance in a tree then also we have to perform 2 rotations. First rotate clockwise (RCW) and second rotate anticlockwise (RAC).
What should be the approach for solving a tree problem?
Any Data Structure can be implemented either iteratively (using loops) or recursively (using recursion functions). And the same goes with the tree data structure. But implementing a tree data structure could be quite confusing at first.
To solve a tree data structure, you should have a good understanding of how recursion works. Because most of the time we will be using recursion to implement a tree data structure. By using recursion we can solve a tree problem in fewer lines of code.
But if you are using an iterative way to solve a tree problem then you might have to write a lot of code and it might be really confusing to understand it. It’s totally up to you which approach you want to follow while implementing a tree.
Thanks for reading and if you like the content then support us on Patreon. Your support will surely help us in writing more of such content.
