Binary Tree in C - Naukri Code 360

Introduction

Binary trees are a fundamental data structure in computer science used to organize & store data in a hierarchical manner. They consist of nodes connected by edges, with each node having at most two child nodes referred to as the left child & right child. Binary trees have a wide range of applications, including searching, sorting, & representing hierarchical relationships.

In this article, we will learn the concept of binary trees in the C programming language, covering their representation, implementation, & traversal techniques with their practical examples.

What are Trees in C?

In the context of data structures, a tree is a hierarchical structure that consists of nodes connected by edges. Each node in a tree can have zero or more child nodes, & the topmost node is called the root. Trees are used to represent relationships between elements in a way that reflects the hierarchical nature of the data.

In the C programming language, trees can be implemented using structures & pointers. Each node in the tree is defined as a structure that contains data & pointers to its child nodes. The most common types of trees include binary trees, binary search trees, AVL trees, & B-trees.

Trees have several important properties:

The root node is the topmost node in the tree & has no parent.
Each node (except the root) has exactly one parent node.
Nodes that have no children are called leaf nodes.
Nodes that are not the root & have at least one child are called internal nodes.
The depth of a node is the number of edges from the root to that node.
The height of a tree is the maximum depth among all the nodes in the tree.

Trees provide an efficient way to organize & search data, making them useful in various applications such as file systems, databases, & computer networks. By leveraging the hierarchical structure of trees, algorithms can perform operations like searching, insertion, & deletion with improved time complexity compared to linear data structures like arrays or linked lists.

Tree Terminologies

When working with trees in C programming, it's important to understand the basic terminologies that describe their parts and functions. Here are the key terms you need to know:

Node: This is a fundamental part of a tree. A node represents a single point within the tree containing data. It can have a connection to other nodes, which are typically referred to as children.
Root: The root node is the topmost node in a tree from which all other nodes branch out. There is only one root per tree and no other node in the tree points to the root.
Child: A child is a node that is directly connected to another node moving away from the root. Nodes can have zero or more children. Nodes that have the same parent are called siblings.
Parent: The converse of a child, the parent node is the one directly connected to one or more nodes below it in the tree.
Sibling: Nodes that share the same parent are siblings. They are on the same level in the hierarchy of the tree.
Leaf: Also known as a terminal node, a leaf is a node that does not have any children. It represents the end of a path in the tree.
Subtree: A subtree is a portion of a tree consisting of a node and all its descendants. This can be thought of as a tree within a tree.
Depth: The depth of a node is the number of edges from the node to the tree's root node.
Height: The height of a node is the number of edges on the longest path from the node to a leaf. The height of the tree is the height of the root node.
Level: The level of a node is defined by 1 + the number of connections between the node and the root. The root is at level 1.

Representation of Binary Tree in C

In C language, a binary tree is represented using a structure definition. This representation involves creating a node structure that includes the data part and pointers to the left and right child nodes. Here’s how you can define a binary tree node in C:

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

In this structure:

int data is where the actual data that is stored in the node goes. This can be any type of data, but here we are using an integer for simplicity.
struct Node* left and struct Node* right are pointers to the left and right children of the node, respectively. If a child does not exist, these pointers will be set to NULL.

To create a new node, we generally use a function that allocates memory for the node, sets the data, and initializes the child pointers to NULL. Here's a simple function to create a new node:

Node* createNode(int value) {
    Node* newNode = (Node*) malloc(sizeof(Node));
    if (newNode == NULL) {
        fprintf(stderr, "Out of memory\n");
        exit(1);
    }
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

This function:

Allocates memory for a new node using malloc.
Checks if the memory allocation was successful.
Initializes the node's data with the provided value.
Sets both child pointers to NULL.

Using such nodes, you can then build the binary tree by connecting nodes appropriately. This involves setting the left and right pointers to point to other nodes in the tree.

Need for Binary Trees in C

Now, let’s see at some of the key reasons why binary trees is required:

Efficient Search

Binary search trees (BSTs) provide an efficient way to search for elements. By organizing the nodes in a specific order (left subtree contains smaller values, right subtree contains larger values), the search operation can be performed in logarithmic time complexity, which is much faster than linear search in arrays or linked lists.

Hierarchical Data Representation

Binary trees are ideal for representing hierarchical data structures. Many real-world scenarios, such as file systems, organizational charts, & HTML/XML document structures, can be naturally modeled using binary trees. The hierarchical relationship between elements can be easily captured & traversed using the parent-child connections in a binary tree.

Sorting & Ordering

Binary search trees maintain elements in a sorted order, making them useful for sorting & ordering data. The in-order traversal of a BST visits the nodes in ascending order, allowing for efficient sorting algorithms like binary tree sort.

Expression Parsing

Binary trees are used to represent & evaluate expressions in programming languages & mathematical formulas. The structure of an expression can be captured using a binary tree, with operators as internal nodes & operands as leaf nodes. This representation allows for easy evaluation & manipulation of expressions.

Huffman Coding

Binary trees are used in Huffman coding, a data compression technique. Huffman coding assigns variable-length codes to characters based on their frequencies, with more frequent characters assigned shorter codes. The Huffman tree, a binary tree, is constructed based on these frequencies, enabling efficient encoding & decoding of data.

Balanced Trees

Balanced binary trees, such as AVL trees & Red-Black trees, provide guaranteed logarithmic time complexity for search, insertion, & deletion operations. These trees automatically maintain their balance by performing rotations or color adjustments, ensuring optimal performance even in the worst case.

Efficient Memory Utilization

Binary trees can be more memory-efficient compared to other data structures like arrays, especially when the data size is unknown or varies dynamically. The nodes in a binary tree are allocated dynamically, allowing for efficient memory utilization based on the actual number of elements stored.

Implementation of Binary Tree in C

Implementing a binary tree in C involves creating the structure for nodes and then adding functions to insert nodes, delete nodes, and traverse the tree. Let’s see how we can implement a basic binary tree:

Define the Node Structure

As discussed in earlier sections, you start by defining a node with data and pointers to the left and right children.

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

Create a New Node

Use a function to create new nodes. This function allocates memory for a new node, sets its data, and initializes its children to NULL.

Node* createNode(int data) {
    Node* newNode = (Node*) malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

Insert Nodes

To insert nodes, you need a function that takes the root of the tree and the data to insert. The function places data in the correct position based on certain rules (e.g., in a binary search tree, data smaller than the parent node goes to the left, and larger data goes to the right).

Node* insertNode(Node* root, int data) {
    if (root == NULL) {  // If the tree is empty, the new node becomes the root
        return createNode(data);
    }
    if (data < root->data) {
        root->left = insertNode(root->left, data);  // Insert in the left subtree
    } else {
        root->right = insertNode(root->right, data);  // Insert in the right subtree
    }
    return root;
}

Traverse the Tree

Traversal can be done in several ways—preorder, inorder, and postorder. Here is how you can perform an inorder traversal, which prints the nodes in ascending order if it’s a binary search tree.

void inorderTraversal(Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);  // Visit left subtree
        printf("%d ", root->data);  // Visit node itself
        inorderTraversal(root->right);  // Visit right subtree
    }
}

Free the Tree

Finally, it’s important to free up the memory used by the tree when it is no longer needed. This function uses postorder traversal to free each node.

void freeTree(Node* root) {
    if (root != NULL) {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}

This basic setup allows you to start working with binary trees. You can expand these functions to include more features, such as deleting nodes, finding the minimum or maximum value, or balancing the tree.

Traversal of Binary Tree

Traversing a binary tree means visiting all the nodes in the tree in a specific order. This is crucial because the way you traverse a tree can affect what you can do with the data you collect. There are several methods to traverse a binary tree, each useful for different purposes:

Inorder Traversal

This method visits the left subtree, the root node, and then the right subtree. It is commonly used because it gives nodes in a non-decreasing order for binary search trees.

void inorderTraversal(Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);  // Visit left subtree
        printf("%d ", root->data);  // Visit root node
        inorderTraversal(root->right);  // Visit right subtree
    }
}

Preorder Traversal

This method visits the root node first, followed by the left subtree, and finally the right subtree. It’s useful for creating a copy of the tree or examining the structure quickly.

void preorderTraversal(Node* root) {
    if (root != NULL) {
        printf("%d ", root->data);  // Visit root node
        preorderTraversal(root->left);  // Visit left subtree
        preorderTraversal(root->right);  // Visit right subtree
    }
}

Postorder Traversal

This method visits the left subtree, the right subtree, and the root node last. This is useful for deleting or freeing nodes and space because you process all descendants before the node itself.

void postorderTraversal(Node* root) {
    if (root != NULL) {
        postorderTraversal(root->left);  // Visit left subtree
        postorderTraversal(root->right);  // Visit right subtree
        printf("%d ", root->data);  // Visit root node
    }
}

Each traversal method serves a different purpose, and understanding them helps you manipulate and utilize binary trees more effectively. Depending on what you need from the data structure, you might choose one method over another.

Example: Binary Tree in C

Let's put together all the concepts we have learned so far & implement a complete binary tree program in C. We'll create a menu-driven program that allows the user to perform various operations on a binary tree.

C

#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));

    newNode->data = data;

    newNode->left = NULL;

    newNode->right = NULL;

    return newNode;

}

struct Node* insertNode(struct Node* root, int data) {

    if (root == NULL) {

        root = createNode(data);

    }

    else if (data <= root->data) {

        root->left = insertNode(root->left, data);

    }

    else {

        root->right = insertNode(root->right, data);

    }

    return root;

}

void inorderTraversal(struct Node* root) {

    if (root == NULL)

        return;

    inorderTraversal(root->left);

    printf("%d ", root->data);

    inorderTraversal(root->right);

}

void preorderTraversal(struct Node* root) {

    if (root == NULL)

        return;

    printf("%d ", root->data);

    preorderTraversal(root->left);

    preorderTraversal(root->right);

}

void postorderTraversal(struct Node* root) {

    if (root == NULL)

        return;

    postorderTraversal(root->left);

    postorderTraversal(root->right);

    printf("%d ", root->data);

}

int main() {

    struct Node* root = NULL;

    int choice, value;

    do {

        printf("\nBinary Tree Operations\n");

        printf("1. Insert a node\n");

        printf("2. In-order Traversal\n");

        printf("3. Pre-order Traversal\n");

        printf("4. Post-order Traversal\n");

        printf("0. Exit\n");

        printf("Enter your choice: ");

        scanf("%d", &choice);

        switch (choice) {

            case 1:

                printf("Enter the value to be inserted: ");

                scanf("%d", &value);

                root = insertNode(root, value);

                break;

            case 2:

                printf("In-order Traversal: ");

                inorderTraversal(root);

                printf("\n");

                break;

            case 3:

                printf("Pre-order Traversal: ");

                preorderTraversal(root);

                printf("\n");

                break;

            case 4:

                printf("Post-order Traversal: ");

                postorderTraversal(root);

                printf("\n");

                break;

            case 0:

                printf("Exiting the program.\n");

                break;

            default:

                printf("Invalid choice. Please try again.\n");

        }

    } while (choice != 0);

  return 0;

}

You can also try this code with Online C Compiler

Run Code

Output

Binary Tree Operations
1. Insert a node
2. In-order Traversal
3. Pre-order Traversal
4. Post-order Traversal
0. Exit
Enter your choice: 1
Enter the value to be inserted: 5
Binary Tree Operations
1. Insert a node
2. In-order Traversal
3. Pre-order Traversal
4. Post-order Traversal
0. Exit
Enter your choice: 1
Enter the value to be inserted: 6
Binary Tree Operations
1. Insert a node
2. In-order Traversal
3. Pre-order Traversal
4. Post-order Traversal
0. Exit
Enter your choice: 1
Enter the value to be inserted: 
8
Binary Tree Operations
1. Insert a node
2. In-order Traversal
3. Pre-order Traversal
4. Post-order Traversal
0. Exit
Enter your choice: 2
In-order Traversal: 5 6 8 
Binary Tree Operations
1. Insert a node
2. In-order Traversal
3. Pre-order Traversal
4. Post-order Traversal
0. Exit
Enter your choice: 0
Exiting the program.

In this program, we define the Node structure & the necessary functions for creating a node, inserting a node into the binary tree, & performing in-order, pre-order, & post-order traversals.

The main function presents a menu to the user, allowing them to choose from different options:

Insert a node: Prompts the user to enter a value & inserts it into the binary tree.
In-order Traversal: Performs an in-order traversal of the binary tree & displays the node values.
Pre-order Traversal: Performs a pre-order traversal of the binary tree & displays the node values.
Post-order Traversal: Performs a post-order traversal of the binary tree & displays the node values.
Exit: Terminates the program.

The program continues to prompt the user for their choice until they choose to exit.

Note -: You can further extend this program to include additional functionalities like searching for a node, deleting a node, or calculating the height of the tree, depending on your specific requirements.

Frequently Asked Questions

What are the basic components of a binary tree in C?

A binary tree consists of nodes, where each node has three components: a data field to store the value, a pointer to the left child, and a pointer to the right child.

What is the difference between a binary tree and a binary search tree in C?

A binary tree allows any arrangement of nodes, while a binary search tree (BST) maintains a sorted order, with the left child containing values less than the parent and the right child containing values greater.

What is the use of binary trees in C?

Binary trees are used for various applications, including expression parsing, hierarchical data representation, and efficient searching and sorting algorithms, facilitating operations like insertion, deletion, and traversal.

How is memory allocated for a binary tree node in C?

Memory for a binary tree node in C is typically allocated using malloc() to create dynamic memory space, where each node's structure is defined, allowing flexible tree growth during runtime.

Conclusion

In this article, we have learned about Binary Tree in C. Binary trees are fundamental data structures in C that enable efficient data organization, searching, and manipulation. Their versatility makes them suitable for various applications, from representing hierarchical data to implementing complex algorithms. Understanding binary trees lays the groundwork for mastering more advanced structures and algorithms, enhancing your programming skills and problem-solving capabilities.