C Trees - Learn Binary Tree Implementation in C

C Trees – Learn Binary Tree Implementation in C

A tree is a hierarchical data structure consisting of nodes, where each node has a value and links to child nodes. In this tutorial, we will focus on the binary tree, where each node has at most two children, referred to as left and right children.

🔹 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 and right child. A root node serves as the starting point of the tree, and the children nodes are connected recursively.

📝 Example 1: Binary Tree Structure

This example demonstrates how to create a simple binary tree structure in C, including basic insertion of nodes.

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

// Define the structure 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 = newNode->right = NULL;
    return newNode;
}

// Function to insert a new node in the binary tree
struct Node* insert(struct Node* root, int data) {
    if (root == NULL) {
        return createNode(data);
    }
    if (data < root->data) {
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        root->right = insert(root->right, data);
    }
    return root;
}

// Function to perform inorder traversal
void inorderTraversal(struct Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

int main() {
    struct Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    printf("Inorder Traversal: ");
    inorderTraversal(root);
    printf("\n");

    return 0;
}

Try It Now

🔹 Tree Traversal

Tree traversal refers to the process of visiting all the nodes in a tree, usually in a specific order. Common types of tree traversal include:

Inorder Traversal: Left subtree, Root, Right subtree
Preorder Traversal: Root, Left subtree, Right subtree
Postorder Traversal: Left subtree, Right subtree, Root

📝 Example 2: Preorder and Postorder Traversal

This example demonstrates how to implement preorder and postorder traversals in a binary tree.

#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 = newNode->right = NULL;
    return newNode;
}

struct Node* insert(struct Node* root, int data) {
    if (root == NULL) {
        return createNode(data);
    }
    if (data < root->data) {
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        root->right = insert(root->right, data);
    }
    return root;
}

// Preorder Traversal: Root, Left, Right
void preorderTraversal(struct Node* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
}

// Postorder Traversal: Left, Right, Root
void postorderTraversal(struct Node* root) {
    if (root != NULL) {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        printf("%d ", root->data);
    }
}

int main() {
    struct Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    printf("Preorder Traversal: ");
    preorderTraversal(root);
    printf("\n");

    printf("Postorder Traversal: ");
    postorderTraversal(root);
    printf("\n");

    return 0;
}

Try It Now

🔹 Binary Search Tree (BST)

A Binary Search Tree is a special type of binary tree where the left child contains values smaller than the parent node, and the right child contains values greater than the parent node. This property allows for efficient searching, insertion, and deletion of nodes.

📝 Example 3: Searching in a Binary Search Tree

This example demonstrates how to search for an element in a binary search tree (BST).

#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 = newNode->right = NULL;
    return newNode;
}

struct Node* insert(struct Node* root, int data) {
    if (root == NULL) {
        return createNode(data);
    }
    if (data < root->data) {
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        root->right = insert(root->right, data);
    }
    return root;
}

// Function to search for a value in the binary search tree
struct Node* search(struct Node* root, int key) {
    if (root == NULL || root->data == key) {
        return root;
    }
    if (key < root->data) {
        return search(root->left, key);
    } else {
        return search(root->right, key);
    }
}

int main() {
    struct Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    int key = 40;
    struct Node* result = search(root, key);
    if (result != NULL) {
        printf("Element %d found in the tree\n", result->data);
    } else {
        printf("Element %d not found in the tree\n", key);
    }

    return 0;
}

Try It Now

🎯 Key Takeaways

A binary tree is a tree structure where each node has at most two children.
The inorder, preorder, and postorder traversals are common ways to visit all nodes in a tree.
A Binary Search Tree (BST) allows for efficient searching and insertion by maintaining a specific structure.

📝 Practice Time!

Try modifying the examples to experiment with different tree sizes, traversal orders, and BST operations. Build your own tree with random data and test the search functionality!