Binary Trees in C

Introduction

Binary trees are a fundamental data structure in computer science. They allow for efficient searching, insertion, and deletion operations, making them incredibly useful in various applications.

What is a Binary Tree?

A binary tree is a tree data structure where each node has at most two children, referred to as the left child and the right child.

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

Creating a New Node

To create a new node, we allocate memory for it using malloc and set the data, left, and right fields.

Node* createNode(int data) {
    Node* newNode = (Node*) malloc(sizeof(Node));
    if(newNode == NULL) {
        printf("Error creating a new node.\n");
        exit(0);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

Inserting a Node

Insertion in a binary tree follows a specific order. If the tree is empty, the new node becomes the root. If the tree is not empty, then we recursively insert the new node into the left subtree if its value is less than the current node, or the right subtree if its value is greater.

Node* insertNode(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;
}

Conclusion

Binary trees are a powerful tool in a programmer's toolkit. Understanding how to implement and manipulate binary trees can greatly enhance your problem-solving abilities in the realm of data structures and algorithms.

References:

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms. MIT press.

Weiss, M. A. (1993). Data structures and algorithm analysis in C.

Sedgewick, R. (2011). Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching. Addison-Wesley..