C Program to Implement a Binary Tree

C Program to Implement a Binary Tree

By /

A binary tree is a hierarchical data structure in which each node has at most two children: a left child and a right child. Binary trees are widely used in applications such as expression parsing, searching, and sorting because they allow efficient data organization. Understanding binary trees is fundamental to mastering more complex structures like binary search trees, heaps, and balanced trees.

Understanding the Problem

Implementing a binary tree involves creating nodes with pointers to left and right children. Traversing, inserting, and deleting nodes require careful handling to maintain the tree structure. Common traversal methods include in-order, pre-order, and post-order, each useful for different purposes, such as data display, evaluation, or copying.

Program 1: Node Structure and Insertion

This program defines the binary tree node structure and allows inserting nodes into the tree. For simplicity, we create a binary tree without enforcing the binary search tree property, inserting nodes manually as left or right children.

#include <stdio.h>
#include <stdlib.h>

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

// Function to create a new node
Node* createNode(int value) {

    Node *newNode = (Node*) malloc(sizeof(Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;

    return newNode;

}

int main() {

    Node *root = createNode(10);
    root->left = createNode(5);
    root->right = createNode(20);
    root->left->left = createNode(3);
    root->left->right = createNode(7);
    root->right->left = createNode(15);

    printf("Binary Tree created successfully.\n");

    return 0;

}

This program defines a Node structure with data, left, and right pointers. The createNode function dynamically allocates memory for a new node. Nodes are manually linked to form the binary tree, illustrating the basic structure without enforcing ordering rules.

Program 2: Tree Traversals

Tree traversal is essential to access or display nodes in a specific order. This program implements in-order, pre-order, and post-order traversals recursively.

#include <stdio.h>
#include <stdlib.h>

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

Node* createNode(int value) {

    Node *newNode = (Node*)
    malloc(sizeof(Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;

    return newNode;

}

void inorder(Node *root) {

    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }

}

void preorder(Node *root) {

    if (root != NULL) {
        printf("%d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }

}

void postorder(Node *root) {

    if (root != NULL) {
        postorder(root->left);
        postorder(root->right);
        printf("%d ", root->data);
    }

}

int main() {

    Node *root = createNode(10);
    root->left = createNode(5);
    root->right = createNode(20);

    root->left->left = createNode(3);
    root->left->right = createNode(7);
    root->right->left = createNode(15);

    printf("In-order Traversal: ");
    inorder(root);

    printf("\nPre-order Traversal: ");
    preorder(root);

    printf("\nPost-order Traversal: ");
    postorder(root);

    printf("\n");

    return 0;

}

The traversal functions recursively visit nodes. In-order traversal visits the left subtree, the node, then the right subtree. Pre-order visits the node first, then left and right subtrees. Post-order visits left and right subtrees before the node. These traversals are fundamental for tree operations like searching, printing, and deletion.

Program 3: Searching for a Node

Searching a binary tree involves recursively checking each node. This program searches for a given value and returns whether it exists in the tree.

#include <stdio.h>
#include <stdlib.h>

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

Node* createNode(int value) {

    Node *newNode = (Node*)
    malloc(sizeof(Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;

    return newNode;

}

int search(Node *root, int key) {

    if (root == NULL) return 0;

    if (root->data == key) return 1;

    return search(root->left, key) || search(root->right, key);

}

int main() {

    Node *root = createNode(10);
    root->left = createNode(5);
    root->right = createNode(20);
    root->left->left = createNode(3);
    root->left->right = createNode(7);
    root->right->left = createNode(15);

    int key = 7;

    if (search(root, key))
        printf("Node %d found in the tree.\n", key);
    else
        printf("Node %d not found in the tree.\n", key);

    return 0;

}

The search function recursively checks the current node and then searches the left and right subtrees. It returns true if the node is found in either subtree, effectively performing a depth-first search.

Program 4: Counting Nodes

This program counts the total number of nodes in a binary tree.

#include <stdio.h>
#include <stdlib.h>

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

Node* createNode(int value) {

    Node *newNode = (Node*)
    malloc(sizeof(Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;

    return newNode;

}

int countNodes(Node *root) {

    if (root == NULL) return 0;

    return 1 + countNodes(root->left) + countNodes(root->right);

}

int main() {

    Node *root = createNode(10);
    root->left = createNode(5);
    root->right = createNode(20);

    root->left->left = createNode(3);
    root->left->right = createNode(7);
    root->right->left = createNode(15);

    printf("Total nodes in the tree: %d\n", countNodes(root));

    return 0;

}

The countNodes function counts the current node and recursively counts nodes in the left and right subtrees. This ensures that all nodes are included in the count.

Program 5: Finding the Height of the Tree

The height of a tree is the length of the longest path from the root to a leaf node. This program computes the height recursively.

#include <stdio.h>
#include <stdlib.h>

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

Node* createNode(int value) {

    Node *newNode = (Node*)
    malloc(sizeof(Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;

    return newNode;

}

int height(Node *root) {

    if (root == NULL) return 0;

    int leftHeight = height(root->left);
    int rightHeight = height(root->right);

    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);

}

int main() {

    Node *root = createNode(10);
    root->left = createNode(5);
    root->right = createNode(20);

    root->left->left = createNode(3);
    root->left->right = createNode(7);
    root->right->left = createNode(15);

    printf("Height of the tree: %d\n", height(root));

    return 0;

}

The function recursively calculates the height of the left and right subtrees and returns the larger of the two plus one for the current node. This is fundamental for understanding tree balance and depth.

FAQs

Q1: Can a binary tree have duplicate values?
Yes, a basic binary tree can have duplicates; constraints depend on whether it is a binary search tree.

Q2: What is the difference between binary tree and binary search tree?
A binary tree has no ordering constraints, while a binary search tree maintains the property that left children are smaller and right children are larger than the parent.

Q3: What is the time complexity of searching in a binary tree?
O(n) in the worst case for an unbalanced tree, as all nodes may need to be checked.

Q4: Can height be zero?
Yes, an empty tree has height 0.

Conclusion

Binary trees are foundational data structures used for hierarchical data representation and efficient searching and sorting. Implementing insertions, traversals, searching, and computing height strengthens understanding of recursion and pointers. Mastering binary trees is a stepping stone toward advanced tree structures and algorithms.

References & Additional Resources

A curated collection of books and online resources providing both theoretical foundations and practical examples for understanding binary trees, dynamic memory allocation, and related data structures in C.

  1. Thareja, R. (2011). Data Structures Using C. Oxford University Press – Detailed coverage of binary trees, dynamic memory allocation, and other fundamental data structures.
  2. Kernighan, B. W., & Ritchie, D. M. (1988). The C Programming Language (2nd Edition). Prentice Hall – Classic reference on C fundamentals, including pointers and memory, essential for data structure implementation.
  3. GeeksforGeeks: Binary Tree in C – Explanation of binary tree concepts, structure, and implementation in C.
  4. Programiz: Data Structures – Binary Tree – Beginner-friendly guide with examples for traversal, insertion, and deletion.
  5. Tutorialspoint: What is Dynamic Memory Allocation in C? – Explanation of malloc(), calloc(), realloc(), and free() functions for memory management.

Related Posts

Scroll to Top