Simple Tree Program using C

Binary trees are a fundamental data structure in computer science, used to represent hierarchical data. In this blog post, we’ll walk through a simple C program to create a binary tree, insert nodes, and print the tree using in-order traversal. This tutorial is designed for beginners.

What is a Binary Tree?

A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. The topmost node is called the root. Here’s a visual representation of a binary tree:

       50
      /  \
     30   70
    / \   / \
   20 40 60 80

Key Concepts

• Node: The basic unit of a binary tree, containing data and pointers to left and right children.
• Root: The topmost node of the tree.
• Leaf: A node with no children.
• In-Order Traversal: A way to traverse the tree where you visit the left subtree, the root node, and then the right subtree.

Creating a Binary Tree in C

Let’s dive into the code to create a simple binary tree, insert nodes, and perform in-order traversal.

Step 1: Define the Node Structure

First, we define the structure of a tree node. Each node will contain an integer data and pointers to its left and right children.

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

// Definition of a tree node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

Step 2: Create a New Node

Next, we create a function to allocate memory for a new node, set its data, and initialize its children to NULL.

// Function to create a new node
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;
}

Step 3: Insert a Node

The insertNode function inserts a new node into the binary tree. It finds the correct position for the new node based on the data value.

// Function to insert a node in the binary tree
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;
}

Step 4: In-Order Traversal

The inOrderTraversal function prints the tree’s elements in in-order (left subtree, root, right subtree).

// Function for in-order traversal of the tree
void inOrderTraversal(struct Node* root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        printf("%d ", root->data);
        inOrderTraversal(root->right);
    }
}

Step 5: Main Function

Finally, the main function creates a binary tree by inserting several nodes and prints the tree’s elements using in-order traversal.

int main() {
    struct Node* root = NULL;

    // Inserting nodes into the binary tree
    root = insertNode(root, 50);
    root = insertNode(root, 30);
    root = insertNode(root, 70);
    root = insertNode(root, 20);
    root = insertNode(root, 40);
    root = insertNode(root, 60);
    root = insertNode(root, 80);

    // Printing the tree using in-order traversal
    printf("In-Order Traversal: ");
    inOrderTraversal(root);
    printf("\n");

    return 0;
}

Complete Program

Here is the complete code for creating a binary tree, inserting nodes, and printing the tree using in-order traversal:

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

// Definition of a tree node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
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;
}

// Function to insert a node in the binary tree
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;
}

// Function for in-order traversal of the tree
void inOrderTraversal(struct Node* root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        printf("%d ", root->data);
        inOrderTraversal(root->right);
    }
}

int main() {
    struct Node* root = NULL;

    // Inserting nodes into the binary tree
    root = insertNode(root, 50);
    root = insertNode(root, 30);
    root = insertNode(root, 70);
    root = insertNode(root, 20);
    root = insertNode(root, 40);
    root = insertNode(root, 60);
    root = insertNode(root, 80);

    // Printing the tree using in-order traversal
    printf("In-Order Traversal: ");
    inOrderTraversal(root);
    printf("\n");

    return 0;
}

Conclusion

This simple binary tree program demonstrates how to create a binary tree, insert nodes, and perform in-order traversal. By understanding these basic concepts, you’ll be well on your way to mastering more complex tree structures and algorithms. Happy coding!