Binary Tree in C – Explore the Reason behind its Popularity

Binary Tree in C is a non-linear data structure in which the node is linked to two successor nodes, namely root, left and right. Binary trees are a very popular concept in the C programming language. But, before we begin this tutorial, it is important to have a crystal clear understanding of pointers and linked lists in C.

In this tutorial, we will discuss:

• Tree in C
• The requirement of a binary tree
• Types of binary tree
• Implementation of a binary tree

1. What are Trees in C?

In mathematical terminology, a tree is referred to as a finite and non-empty set of elements. It can also be regarded as an abstract model of a hierarchical structure that follows a parent-child relationship.

In programming terminology, a tree is nothing but a non-linear data structure that has multiple nodes, rather than just one like we saw in a linked list, stack, and queue.

When we talk about trees in C, we generally refer to a binary tree. We will discuss in detail the meaning of a binary tree in the later section.

Here is a diagrammatic representation of a tree:

Explore 15 types of Escape Sequence in C that makes your coding better

Before we proceed towards the discussion on a binary tree, let us acquaint ourselves with some of the tree terminologies:

1. Root: A node without a parent is called a root. In the above diagram, “1” is the root.
2. Siblings: The nodes that have the same parent are called siblings. In the above diagram “2”, “3” and “4” are siblings as they have a common parent “1”.
3. Internal node: A node that has at least a single child is called an internal node. In the above diagram, “1”, “2”, 3“ and “6” are internal nodes.
4. External node: It is also called a leaf. In simple words, a node without any children is called an external node. In the above diagram, “4”, “5”, “7”, “8, “9”, “10” and “11” are external nodes.
5. Ancestors: These include the parent, grandparents or great grandparents and so on of a node. In the above diagram, the ancestors of “6” are “1” and “3”.
6. Descendants: These include the child, grandchild or great-grandchild and so on of a node. In the above diagram, the descendants of “2” are “5”, “6”, “9”, “10” and “1”.
7. Edge: Connection between one node to another is called an edge. In the above diagram, the purple line from “1” to “4” is an edge.
8. Path: It is a sequence of nodes and edges that are connected with each other. In the above diagram, the red line from “1” to “10” is a path. It is important to note that a path simply does not only contain edges but nodes also.
9. Depth: It refers to the number of edges from the node to the root of the tree’s node.
10. Height: It refers to the maximum depth of a node.
11. Level: The level of a node is (the depth of the node + 1).

Key takeaway: The height and depth of a tree are equal, but the height and depth of a node will always be different.

2. Binary Tree in C Programming

This tree consists of zero or more nodes. It is important to note that a binary tree can have no children (leaf node), 1 child or 2 children. No other cases are possible.

Diagrammatic representation of how a binary tree looks like:

Here is a diagrammatic representation of how data is stored in the node of a binary tree:

Here, *left_pointer is the pointer to a left child which may or may not be NULL and *right_pointer is the pointer to a right child which may or may not be NULL.

Uncover the Difference between Typecasting & Type Conversion in C

3. Need for Binary Tree in C

This tree proves to be of great importance, which we will discuss in detail one by one.

There are several applications of a binary tree when it comes to C programming. Some of them are:

1. The implementation of BST (Binary Search Tree) is a fast and efficient method to find an element in a huge set.
2. This tree gives birth to the concept of heaps through which heapsort can be implemented.
3. In order to implement databases, a binary tree is of utmost importance as they are the base of B-Trees and T-Trees to store information.

4. Types of Binary Tree in C

There are basically two types of a C binary tree. They are namely:

4.1 Complete binary tree

A tree in which every level except the last level is filled completely and all nodes are as far left as possible is called a complete binary tree.

4.2 Full binary tree

A tree in which every node has two children except the external node (leaves) is called a full binary tree.

5. Implementation of Binary Tree in C

In the C programming language, we can implement a binary tree in a similar fashion like linked lists. We employ the use of structures in C.

5.1 Declaration

Before we learn how to implement a binary tree, let us see how to declare it.

struct node
{
int data;
struct node *left;
struct node *right;
};

5.2 Creating Nodes

This is how a linked list of three data elements is created in C:

struct node *root;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* Dynamic memory allocation */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* Assign data values */
one->data_element = 1;
two->data_element = 2;
three->data_element = 3;

/* Connecting nodes */
one->left = two;
one->right = three;
two->left = NULL;
two->right = NULL;
three->left = NULL;
three->right = NULL;

/* Saving the address of the first node in the root */
root = one;

Before we discuss the implementation process, you should be aware of the Functions in C.

5.3 Implementation of Binary Tree in C

Here is a program in C that illustrates the implementation of a binary tree:

#include<stdio.h>
#include<stdlib.h>
struct node
{
int data_element;
struct node *left, *right;
};

struct node *new_node(int data_element)
{
struct node *temp = (struct node *)malloc(sizeof(struct node)); // Allocating memory to the node
temp->data_element = data_element;
temp->left = temp->right = NULL;
return temp;
}

void display(struct node *root) // A function for the inroder traversal of the binary tree
{
if (root != NULL)
{
display(root->left);
printf("%d \n", root->data_element);
display(root->right);
}
}

struct node* insert(struct node* node, int data_element) // Function to insert a new node
{

if (node == NULL) return new_node(data_element); // Return a new node if the tree if empty
if (data_element < node->data_element)
{
node->left = insert(node->left, data_element);
}
else if (data_element > node->data_element)
{
node->right = insert(node->right, data_element);
}
return node;
}

int main()
{

printf("Welcome to DataFlair tutorials!\n\n");

struct node *root = NULL;
root = insert(root, 10);
insert(root, 20);
insert(root, 30);
insert(root, 40);
insert(root, 50);
insert(root, 60);
insert(root, 70);

display(root); // Function to display the binary tree elements

return 0;
}

Output-

6. Quiz on Binary Tree in C

7. Summary

In this tutorial, we discussed the basic meaning of trees in C, then we further discussed what are the binary tree and their requirement. We even discussed the two types of binary trees. Lastly, we ended our discussion by learning how to implement a binary tree from the start.

You can simplify your long code with Recursive Function in C

Don’t forget to comment below!