Binary Tree in C – Types and Implementation

Introduction

The tree in C is a non-linear data structure, i.e., The elements are not stored sequentially, and in the tree in C, they are present in levels. A binary tree in C is a data structure in which every node can have a maximum of two children nodes. Children nodes are labeled as right and left child. Each node in the binary tree contains a value and two pointers pointing to the children. The topmost node of the binary tree is called the root node, and the bottom-most nodes of the binary tree are called leaf nodes. The height of a binary tree is calculated by taking the longest path between the root and the leaf node.

In the i'th level, the maximum number of nodes can be 2 raised to the power i, and the minimum number of nodes in a binary tree of height H is H+1.

The binary trees are implemented using pointers in C. Usually, we create a structure that contains a data variable that is used to store the value of that node and two pointer variables(named left and right). The left pointer is used to point to the left child similarly, the right pointer is used to point to the right child of the node.

The binary tree in C can also be implemented using the array data structure. If P is the index of the parent element, then the left child will be stored in their index $(2p)+1$, and the right child will be stored in the index $(2p)+2$.

What are Trees in C?

The tree is a non-linear data structure in C that contains nodes that are not connected linearly. Rather they are connected hierarchically. The nodes are present at different levels and are connected by edges. Between the set of two connected nodes, the one which is at the upper level is considered a parent, and the lower one is considered a child node.

In Tree in C, a parent node can have many children nodes. The diagram below shows the structure of the tree in C.

In the above image of the tree, A is the root node. B, C, and E are the children of node A; they have 2, 1, and 2 children, respectively. Here, D, G, F, H, L, K, and M are the leaf nodes.

A binary tree in C is a special case of the tree, which can have only two children nodes (left child and right child).

Tree Terminologies

Various terminologies are related to the tree :

1. Root :
   The first node of the binary tree is known as the root node of the binary tree. There cannot be any tree without a root node, as it is the tree's origin, and the root node has no parent element. We cannot have more than one root node in a tree.

2. Edge :
   The connecting link between the two nodes is known as the edges of the tree. It is also referred to as the branch of a tree. If there are n nodes in a binary tree, there will be a total of n-1 edges.

3. Parent :
   A node that has a connecting link to another node in the level below is known as a parent node. In a more formal term, a node that is a predecessor of another node is called a parent node.

4. Child :
   Any node connected to a node one level above it is known as the child node. In formal terms, every note that is a descendant of any node is known as a child node. Every not present in the tree can be considered as a child node except the root node.

5. Siblings :
   The children node that shares the same parent node are referred to as siblings.

6. Leaf :
   A node with no child is known as a leaf node. It is the terminal node of the tree.

7. Internal Node :
   The nodes with at least one child node are known as internal nodes. Every node (even the root node) is internal except the leaf nodes.

8. External Node :
   A node with no child node is considered an external node.

9. Ancestors :
   Ancestors of a node are the nodes in the path from the root to the current node, including the root node, and excluding the current node are ancestors of the current node.

10. Descendants :
    Descendants of a node are the nodes below its level and connected to it directly or via nodes. All the children, their children, and so on are the descendants of the current node.

11. Path :
    A path between any two nodes of a tree is the sequence of connected nodes along with the edges between the two nodes. And the path length is the number of nodes present between two nodes.

12. Level :
    The level in the tree represents the number of steps from the top/root. The root node of the tree is said to be at level 0, and as we go downwards the level increases

13. Depth :
    The depth of any node in the tree is the length of the path from the root node to that particular node, i.e., The number of nodes between that particular node and the root node.

14. Height :
    The height of any node is given by the maximum number of edges from the leaf node to that particular node.

Applications of Trees

The application of trees is:

1. It is used where we need to create hierarchical data.
2. Multistage decisions making can be created using trees.
3. It can be used to store the dictionary's data and for fast and efficient spell-checking.
4. In the blockchain, a special kind of binary tree known as the Merkle tree is used, a binary tree of the hashes of the transactions in the blockchain.

Representation of Binary Tree in C

A binary tree can be represented using a linked list and also using an array. Representation of this tree, using both(array and linked list) is explained below.

Array Representation :

The binary tree can be represented using an array of size 2n+1 if the depth of the binary tree is n. If the parent element is at the index p, Then the left child will be stored in the index $(2p)+1$, and the right child will be stored in the index $(2p)+2$.

The array representation of the above binary tree is :
As in the above binary tree, A was the root node, so that it will be stored in the 0th index. The left child of A will be stored in the 2(0)+1 equal to the 1st location. So, B is stored in index 1. And similarly, the right child of A will be stored in the 2(0)+2 index. For every node, the left and right child will be stored accordingly.

Linked List Representation :

For the linked list representation, we will use the doubly linked list, which has two pointers so that we can point to the left and right children of a binary tree node. NULL is given to the pointer as the address when no child is connected.

The Linked list representation of the above binary tree is :

Need for Binary Trees

1. Searching becomes easy and faster with the help of a binary search tree, even for huge data sets.
2. Trees do not have a limit on the nodes. So, according to the user's need, a tree of any size can be created and further increased, unlike an array.
3. It can store hierarchical data in the database.
4. A binary tree can also be used for classification and decision-making.

Types of Binary Trees in C

Full Binary Tree

In a full binary tree, every node has either 0 or two children. It is also referred to as a strict binary tree.

Perfect Binary Tree

As the name suggests, a perfect binary tree is one in which all the nodes(internal nodes) have two children and all the leaf nodes are at the same level.

Complete Binary Tree

In a complete binary tree, all the levels except the last level(that contains the leaf nodes) should be full. In this type of binary tree, the node should be inserted to the left first, i.e., left-leaning (it is not mandatory to have a right sibling for the node).

Degenerate or Pathological Tree

In this type of tree, every node has only one child that can be either on the left or on the right.

If nodes only have children towards the left, it is called a left-skewed binary tree.

If nodes only have children towards the right, it is called a right-skewed binary tree.

Balanced Binary Tree

It is a binary tree in which, for every node, the height of the left subtree and the height of the right subtree defer by zero or, at most, one.

Implementation of Binary Tree in C

The binary tree is implemented using the structure. Each node will contain three elements, the data variable, and the 2 pointer variables. We will use a user-defined datatype (structure) to create the nodes. The node will point to NULL if it doesn't point to any children.

Declaration of a Binary Tree in C

To declare the nodes of the binary tree, we will create a structure containing one data element and two pointers of the name left and right.

Code :

Create a New Node of the Binary Tree in C

To create a new node of the binary tree, we will create a new function that will take the value and return the pointer to the new node created with that value.

Code :

The new node which is being created will have the left and right pointers, pointing at null.

Inserting the Left and/or the Right Child of a Node

This function will take two inputs, first the value that needs to be inserted and second the node's pointer on which the left or the right child will be attached. To insert into the left side of the root node, we will simply call the create function with the value of the node as a parameter. So that a new node will be created, and as that function returns a pointer to the newly created node, we will assign that pointer to the left pointer of the root node that is being taken as input.

Similarly, insertion on the right side will call the create function with the given value, and the returned pointer will be assigned to the write pointer of the root node.

Code :

Traversal of Binary Tree

We can traverse the element tree and can display these elements in three formats/methods :

In every traversal method of the binary tree, we need to visit the left node, the right node, and the data of the present/current node(root). Three methods will have these three actions in a different order.

Pre-Order :
In this type of traversal, first, we will take the value of the current node(present node), then we will go to the left node, and after that, we will go to the right node.

Code :

In-Order :
In this type of traversal, first, we'll go to the left node, then we'll take the value of the current node, and then we will go to the right node.

Code :

Post-Order :
In this type of traversal, first, we'll go to the left node, then to the right node, and at last, we will take the current node's value.

Code :

Example : Implementation of Binary Tree in C

Here in this example, we will use the functions we learned above to create a binary tree, and then we will traverse that binary tree in three different methods.

A structure node is declared, containing a data variable and two pointer variables.

First, we have declared a function create, which takes a value as an input and creates and returns a node that will have the data variable equal to the value, and the left and right pointer variables will point to NULL.

To insert the left child, we will use the insertLeft function, which takes the pointer to the parent node and the value. Then internally, it calls the create function, and the node returned by it is attached to the left pointer of the parent node. Similarly, the insertRight function works.

Code :

After creating the tree, we traversed it using the Inorder, Preorder , and Postorder traversal methods, and we got the following output.

Output :