C Programming: Data Structures – Binary Trees and Binary Search Trees (BST)

Data structures are fundamental to computer science and play a critical role in the design and efficiency of algorithms. Among the various data structures, binary trees and binary search trees (BST) are particularly significant due to their simplicity and effectiveness in solving complex problems. This article explains these structures in detail, highlighting their importance and providing important information related to their implementation and usage in C programming.

Binary Trees

A binary tree is a hierarchical data structure that consists of nodes, where each node contains data and two references (often referred to as "left" and "right") to other nodes, which are known as its children. The node at the top of the tree is called the root. Each node in a binary tree has at most two children, and one node is considered the parent of the other two. The nodes with no children are called leaf nodes, or terminal nodes.

Structure of a Binary Tree Node in C:

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

This structure represents each node in a binary tree, where data holds the value of the node, and left and right are pointers to the left and right children, respectively.

Basic Operations on Binary Trees:

  • Insertion: Adding a new node to the tree.
  • Deletion: Removing a node from the tree.
  • Traversal: Visiting and processing each node in the tree.
    • Pre-order Traversal: Traverse the root node, then recursively traverse the left subtree, followed by the right subtree.
    • In-order Traversal: Recursively traverse the left subtree, then visit the root node, and finally, recursively traverse the right subtree.
    • Post-order Traversal: Recursively traverse the left subtree, then recursively traverse the right subtree, and finally, visit the root node.
    • Level-order or Breadth-first Traversal: Visiting all nodes level by level from top to bottom and left to right.

Code Example for In-order Traversal:

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

Binary Search Trees (BST)

A binary search tree (BST) is a specific type of binary tree with the additional property that for each node, all elements in its left subtree are smaller, and all elements in its right subtree are larger. This property makes binary search trees particularly efficient for searching operations, as they allow us to eliminate half of the tree in each step of the search.

Structure of a Binary Search Tree Node in C: The structure of a node in a BST is the same as that of a binary tree. However, the operations to maintain the BST property must be carefully handled.

Properties of Binary Search Trees:

  • Left Subtree Property: Every node in the left subtree has a value less than the root node.
  • Right Subtree Property: Every node in the right subtree has a value greater than the root node.
  • No Duplicates: No two nodes have the same value.

Basic Operations on Binary Search Trees:

  • Insertion: Adding a new node while maintaining the BST property.
  • Deletion: Removing a node in a way that the BST property remains intact.
  • Search: Searching for a specific value in the tree, leveraging the BST property to reduce search time.
  • Traversal: Similar to binary trees, BSTs can also be traversed in pre-order, in-order, post-order, and level-order methods.

Insertion in BST:

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

Deletion in BST: Deleting a node in a BST can be a bit more complicated as it needs to maintain the BST property:

  • Node with No Children: Simply remove the node.
  • Node with One Child: Remove the node and replace it with its child.
  • Node with Two Children: Find the smallest node in the right subtree, replace the deleted node with this node, and delete the smallest node from the right subtree.
struct Node* deleteNode(struct Node* root, int data) {
    if (root == NULL) return root;

    if (data < root->data)
        root->left = deleteNode(root->left, data);
    else if (data > root->data)
        root->right = deleteNode(root->right, data);
    else {
        if (root->left == NULL) {
            struct Node* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            struct Node* temp = root->left;
            free(root);
            return temp;
        }
        struct Node* temp = minValueNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

Search in BST:

struct Node* search(struct Node* root, int key) {
    if (root == NULL || root->data == key) return root;
    if (root->data < key) return search(root->right, key);
    return search(root->left, key);
}

Importance of Binary Trees and Binary Search Trees:

  • Efficiency: Binary search trees provide efficient search, insertion, and deletion operations with average-case time complexity of (O(\log n)).
  • Flexibility: Binary trees and BSTs are versatile and can be used in various applications such as databases, scheduling algorithms, and network routing.
  • Foundation: Understanding binary trees and BSTs is crucial for grasping more complex data structures like AVL trees, red-black trees, and heap data structures.

In conclusion, binary trees and binary search trees are fundamental data structures in C programming that offer a solid foundation for tackling more advanced data structures and algorithmic problems. Their strength lies in their simplicity and efficiency, making them a powerful tool in the programmer's toolkit.




Certainly! Let's break down an example of creating a binary tree and a binary search tree (BST) in C programming, setting up the route, and running the application while discussing the data flow step-by-step.

Setting Up Your Environment

Before you start writing code, ensure you have a working C compiler on your system like GCC (GNU Compiler Collection).

If you are using Linux, GCC is usually pre-installed. You can check if it's installed by typing:

gcc --version

If GCC is not installed, you can install it via your package manager, e.g.,

sudo apt-get install gcc

If you are using macOS, you can install GCC using Homebrew:

brew install gcc

If you are using Windows, consider using a cross-platform IDE such as Code::Blocks, CLion, or simply use MinGW (Minimalist GNU for Windows) to install GCC.

Creating a Binary Tree in C

Let's create a simple binary tree and add some nodes to it.

Step 1: Define the Structure

First, define the structure of the node and the tree.

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

// Define the structure of a tree node
typedef struct TreeNode {
    int value;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// Function to create a new TreeNode
TreeNode* createNode(int value) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (!newNode) {
        printf("Memory error\n");
        return NULL;
    }
    newNode->value = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}

Step 2: Insert Nodes into the Binary Tree

For simplicity, let’s just manually insert nodes in a binary tree.

void insertTreeNode(TreeNode **root, int value) {
    if (*root == NULL) {
        *root = createNode(value);
    } else if (value < (*root)->value) {
        insertTreeNode(&(*root)->left, value);
    } else {
        insertTreeNode(&(*root)->right, value);
    }
}

Notice that this function inserts elements based on their values, placing smaller ones left and larger ones right, similar to a binary search tree. However, in a standard binary tree, this logic is not mandatory.

Step 3: Traverse the Binary Tree

Let’s implement a simple in-order traversal to see how elements are stored.

// In-order traversal: Left -> Root -> Right
void inOrderTraversal(TreeNode *root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        printf("%d ", root->value);
        inOrderTraversal(root->right);
    }
}

Step 4: Main Function

Now we tie everything together.

int main() {
    TreeNode *treeRoot = NULL;

    // Insert elements into the binary tree
    insertTreeNode(&treeRoot, 10);
    insertTreeNode(&treeRoot, 5);
    insertTreeNode(&treeRoot, 15);
    insertTreeNode(&treeRoot, 3);
    insertTreeNode(&treeRoot, 7);
    insertTreeNode(&treeRoot, 12);
    insertTreeNode(&treeRoot, 18);

    // Perform in-order traversal
    printf("In-order traversal:\n");
    inOrderTraversal(treeRoot);
    printf("\n");

    return 0;
}

Creating a Binary Search Tree (BST)

We will modify the above example to follow the properties of a binary search tree strictly.

Step 1 & 2: Definition and Node Insertion

The function insertTreeNode from the binary tree example works fine for a BST since it already follows the BST property (left child <= parent < right child).

However, for the purpose of clarity, let’s redefine our steps:

Creating Node:

TreeNode* createNode(int value) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (!newNode) {
        printf("Memory error\n");
        return NULL;
    }
    newNode->value = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}

Inserting Node: Using the same insertTreeNode function, but we’ll ensure the logic stays consistent with BST rules.

Step 3: Traversal Functions

In-order Traversal:

void inOrderTraversal(TreeNode *root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        printf("%d ", root->value);
        inOrderTraversal(root->right);
    }
}

Pre-order Traversal:

void preOrderTraversal(TreeNode *root) {
    if (root != NULL) {
        printf("%d ", root->value);
        preOrderTraversal(root->left);
        preOrderTraversal(root->right);
    }
}

Post-order Traversal:

void postOrderTraversal(TreeNode *root) {
    if (root != NULL) {
        postOrderTraversal(root->left);
        postOrderTraversal(root->right);
        printf("%d ", root->value);
    }
}

Step 4: Main Function Adjustments

We'll add different types of traversals to our main function.

int main() {
    TreeNode *bstRoot = NULL;

    // Insert elements into the binary search tree
    insertTreeNode(&bstRoot, 10);
    insertTreeNode(&bstRoot, 5);
    insertTreeNode(&bstRoot, 15);
    insertTreeNode(&bstRoot, 3);
    insertTreeNode(&bstRoot, 7);
    insertTreeNode(&bstRoot, 12);
    insertTreeNode(&bstRoot, 18);

    // Perform in-order traversal
    printf("In-order traversal:\n");
    inOrderTraversal(bstRoot);
    printf("\n");

    // Perform pre-order traversal
    printf("Pre-order traversal:\n");
    preOrderTraversal(bstRoot);
    printf("\n");

    // Perform post-order traversal
    printf("Post-order traversal:\n");
    postOrderTraversal(bstRoot);
    printf("\n");

    return 0;
}

Data Flow in the Application

  1. Node Creation:

    • When createNode is called for the first time with value=10, it allocates memory for a TreeNode and initializes it with value=10, and both left and right pointers to NULL. The address of this allocated memory is returned and stored in the pointer treeRoot/bstRoot.

  2. Inserting Elements into the Tree:

    • insertTreeNode is called with the root pointer and the value 5.
      • Since the value (5) is less than (*root)->value (10), insertTreeNode(&(*root)->left, 5) is called recursively.
      • This process continues until a node with left=NULL or right=NULL is found.
    • For a binary search tree, this ensures that all values less than the current node go to the left subtree, and all values greater go to the right subtree.

  3. Tree Traversals:

    • In-order Traversal: The function visits the left subtree first, then the root node, and finally the right subtree. This sequence yields sorted data if the tree is a BST.
      • Call stack for In-order: inOrderTraversal(3), inOrderTraversal(5), inOrderTraversal(7), inOrderTraversal(10), inOrderTraversal(12), inOrderTraversal(15), inOrderTraversal(18)
    • Pre-order Traversal: The function visits the root node first, followed by the left subtree, and finally the right subtree. Useful for copying trees.
      • Call stack for Pre-order: preOrderTraversal(10), preOrderTraversal(5), preOrderTraversal(3), preOrderTraversal(7), preOrderTraversal(15), preOrderTraversal(12), preOrderTraversal(18)
    • Post-order Traversal: The function visits the left subtree first, then the right subtree, and finally the root node. Useful for deleting trees.
      • Call stack for Post-order: postOrderTraversal(3), postOrderTraversal(7), postOrderTraversal(5), postOrderTraversal(12), postOrderTraversal(18), postOrderTraversal(15), postOrderTraversal(10)

Compiling and Running the Application

To compile the above program, save the code in a file called binary_tree.c and compile it using GCC:

gcc binary_tree.c -o binary_tree

Run the compiled executable:

./binary_tree

Expected Output

You should see the following output:

In-order traversal:
3 5 7 10 12 15 18 
Pre-order traversal:
10 5 3 7 15 12 18 
Post-order traversal:
3 7 5 12 18 15 10

This output demonstrates the different ways to traverse the same BST, each producing a distinct visitation order.

Summary

  • You learned about the structure of a binary tree and a binary search tree.
  • You implemented functions to create a binary tree, insert nodes, and perform different types of traversals.
  • By understanding the call stack and how recursion works during traversals, you grasped the data flow within the BST.

Further Exploration

Try adding more functionality, like searching for elements within the BST, deleting elements, balancing the BST, or even implementing other types of binary trees such as AVL trees or Red-Black trees, which are self-balancing and efficient. Happy coding!




Top 10 Questions and Answers on C Programming: Data Structures - Binary Trees and Binary Search Trees (BST)

1. What is a Binary Tree?

Answer: A binary tree is a hierarchical data structure where each node has at most two children, referred to as the left child and the right child. The topmost node in the binary tree is called the root. Binary trees can be used to represent hierarchical data and are the basis for more complex data structures like binary search trees, heaps, and AVL trees.

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

2. What is a Binary Search Tree (BST)?

Answer: A binary search tree is a type of binary tree where each node has at most two children. For each node, all elements in the left subtree are less than the node, and all elements in the right subtree are greater than the node. This property allows for efficient searching, insertion, and deletion operations.

struct TreeNode {
    int value;
    struct TreeNode* left;
    struct TreeNode* right;
};

// Function to create a new Tree Node
struct TreeNode* createNode(int value) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->value = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}

3. How do you insert elements into a BST?

Answer: To insert an element into a BST, you start at the root and recursively find the appropriate position where the element should be placed based on the BST property. If the current node is NULL, you create a new node and insert it.

struct TreeNode* insert(struct TreeNode* node, int value) {
    if (node == NULL) return createNode(value);
    if (value < node->value)
        node->left = insert(node->left, value);
    else if (value > node->value)
        node->right = insert(node->right, value);
    return node;
}

4. How do you perform an in-order traversal of a BST?

Answer: In-order traversal of a BST visits nodes in ascending order. It involves recursively traversing the left subtree, visiting the root node, and then recursively traversing the right subtree.

void inorderTraversal(struct TreeNode* node) {
    if (node != NULL) {
        inorderTraversal(node->left);
        printf("%d ", node->value);
        inorderTraversal(node->right);
    }
}

5. How do you delete a node from a BST?

Answer: Deleting a node from a BST involves three cases:

  • Node with no child (leaf node): Simply remove the node.
  • Node with one child: Copy the child to the node and delete the child.
  • Node with two children: Find the inorder successor (smallest in the right subtree) or inorder predecessor (largest in the left subtree), copy its value to the node, and delete the successor/predecessor.
struct TreeNode* minValueNode(struct TreeNode* node) {
    struct TreeNode* current = node;
    // Loop down to find the leftmost leaf
    while (current && current->left != NULL)
        current = current->left;
    return current;
}

struct TreeNode* deleteNode(struct TreeNode* root, int key) {
    if (root == NULL) return root;
    if (key < root->value)
        root->left = deleteNode(root->left, key);
    else if (key > root->value)
        root->right = deleteNode(root->right, key);
    else {
        if (root->left == NULL) {
            struct TreeNode* temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL) {
            struct TreeNode* temp = root->left;
            free(root);
            return temp;
        }
        struct TreeNode* temp = minValueNode(root->right);
        root->value = temp->value;
        root->right = deleteNode(root->right, temp->value);
    }
    return root;
}

6. What is the difference between a balanced and an unbalanced binary search tree?

Answer: A balanced binary search tree maintains the property that, for every node, the height of the left and right subtrees differ by at most one or a constant factor. Examples include AVL trees and Red-Black trees. Balanced trees offer optimal O(log n) time complexity for search, insert, and delete operations. Unbalanced trees may degrade to linked lists, leading to O(n) time complexity for these operations.

7. How do you create a balanced binary search tree?

Answer: To create a balanced BST from a sorted array, you can recursively select the middle element as the root of the subtree and repeat the process for the left and right subarrays.

struct TreeNode* sortedArrayToBST(int arr[], int start, int end) {
    if (start > end) return NULL;
    int mid = (start + end) / 2;
    struct TreeNode* node = createNode(arr[mid]);
    node->left = sortedArrayToBST(arr, start, mid - 1);
    node->right = sortedArrayToBST(arr, mid + 1, end);
    return node;
}

8. Explain the time complexity of operations for a BST.

Answer: The time complexity of operations on a BST (search, insert, delete) is O(h), where h is the height of the tree. In the worst case (unbalanced tree), h = n (number of nodes), resulting in O(n) time complexity. For balanced trees, h = log n, thus operations are O(log n).

9. What is an AVL tree?

Answer: An AVL tree is a self-balancing binary search tree where the difference between heights of left and right subtrees cannot be more than one for all nodes. AVL trees maintain balance through rotations during insertions and deletions, ensuring O(log n) time complexity for search, insert, and delete operations.

10. What are the advantages and disadvantages of using a binary search tree?

Answer:

  • Advantages:
    • Efficient searching, insertion, and deletion (O(log n) for balanced trees).
    • In-order traversal yields sorted values.
  • Disadvantages:
    • Can become unbalanced, leading to O(n) time complexity in the worst case.
    • Requires additional operations (rotations) to maintain balance in AVL trees.
    • More complex to implement compared to simpler data structures like arrays.

These questions and answers provide a comprehensive understanding of binary trees and binary search trees in C programming, covering their implementation, operations, and properties.