C Programming Data Structures Binary Trees And Binary Search Trees Bst Complete Guide

Last Update:2025-06-23T00:00:00 .NET School AI Teacher - SELECT ANY TEXT TO EXPLANATION. 12 mins read Difficulty-Level: beginner

Understanding the Core Concepts of C Programming data structures Binary Trees and Binary Search Trees BST

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

Understanding Binary Trees

Key Components:

Root: The topmost node in the tree.
Node: Each element of the tree containing some data and references (or pointers) to its left and right children.
Leaf Node: A node with no children.
Internal/Non-Leaf Node: A node with one or more children.
Depth: Distance of a node from the root node (root’s depth is 0).
Height: Maximum number of edges from the node to its deepest leaf node.

Traversal Techniques:

Inorder Traversal: Left subtree → Root → Right subtree
Preorder Traversal: Root → Left subtree → Right subtree
Postorder Traversal: Left subtree → Right subtree → Root
Level Order Traversal: Nodes level by level, from top to bottom and left to right

Binary Search Tree (BST)

A Binary Search Tree (BST) is a specific type of binary tree where each node adheres to a particular property: for any given node, the value of all nodes in its left subtree is less than the node’s value, and the value of all nodes in its right subtree is greater than the node’s value. This property makes BSTs efficient for searching, inserting, and deleting operations, with an average time complexity of O(log n).

Important Properties:

Left Subtree Property: All nodes in the left subtree are less than the root node.
Right Subtree Property: All nodes in the right subtree are greater than the root node.
No Duplicates: Each value is unique in a BST (though some implementations allow duplicates with a specific placement convention).

Operations in BST:

Search: Start at the root and compare the target value with the current node’s value. If the value matches, the search is successful. Else, move left if the target is smaller or move right if the target is larger, recursively.
Insertion: Similar to search, but when you find a null position (where the value should be), you place the new node.
Deletion: Three cases need to be handled:
- Node has no children: Simply remove it.
- Node has one child: Remove the node and replace it with its child.
- Node has two children: Find the in-order successor (smallest node in the right subtree) or in-order predecessor (largest node in the left subtree), swap values, and delete the successor/predecessor.

Advantages:

Efficient Searching: Average-case time complexity O(log n).
Dynamic Size: Easily add or remove nodes.
Ordered Data: In-order traversal yields sorted data.

Disadvantages:

Performance Degradation: Worst-case time complexity O(n) when the tree becomes a linked list.
Memory Consumption: Requires additional memory to store pointers.

Applications:

Symbol Tables: Used in compilers for storing identifiers and their attributes.
Indexing Structures: Databases use BSTs for fast search operations.
Scheduling: Hierarchical management of resources.

Implementation in C

Here’s a simple example of a BST implementation in C, including basic operations like insertion, search, and inorder traversal.

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

// Node structure
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 new node in BST
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 a value in BST
struct Node* search(struct Node* root, int data) {
    if (root == NULL || root->data == data) {
        return root;
    }
    if (data < root->data) {
        return search(root->left, data);
    }
    return search(root->right, data);
}

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

// Function to delete a node
struct Node* findMin(struct Node* root) {
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

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 {
        // Node with only one child or no child
        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;
        }
        // Node with two children: Get the inorder successor
        struct Node* temp = findMin(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

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 of the given tree: \n");
    inorder(root);

    printf("\n\nDelete 20\n");
    root = deleteNode(root, 20);
    printf("Inorder traversal of the modified tree: \n");
    inorder(root);

    printf("\n\nDelete 30\n");
    root = deleteNode(root, 30);
    printf("Inorder traversal of the modified tree: \n");
    inorder(root);

    printf("\n\nDelete 50\n");
    root = deleteNode(root, 50);
    printf("Inorder traversal of the modified tree: \n");
    inorder(root);

    return 0;
}

Explanation:

Node Structure: Defines a node in the BST with data and pointers to left and right children.
Create Node: Allocates memory for a new node, initializes its value, and sets its children to NULL.
Insert Function: Recursively finds the correct position for a new value and inserts it.
Search Function: Recursively searches for a value, returning the node if found or NULL otherwise.
Inorder Traversal: Recursively visits all nodes in ascending order.
Delete Function: Handles three cases: node with no children, one child, or two children.

Online Code run

🔔 Note: Select your programming language to check or run code at

💻 Run Code Compiler

Step-by-Step Guide: How to Implement C Programming data structures Binary Trees and Binary Search Trees BST

Binary Tree Example

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.

Step 1: Define the Structure of a Node

First, we need to define what a node in the binary tree looks like. Each node will contain some data, and pointers to its left and right children.

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

// Define the structure for a single node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return node;
}

// Function to perform inorder traversal of a binary tree
void inorder(struct Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}
int main() {
    // Create the root of the binary tree manually
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    // Perform inorder traversal
    printf("Inorder traversal of binary tree: ");
    inorder(root);
    printf("\n");

    return 0;
}

Explanation:

Node Structure: The Node structure contains an integer data, and pointers to left and right children.
newNode Function: This function allocates memory for a new node and initializes it with the given data. It sets both children to NULL.
inorder Function: This function performs an inorder traversal, which visits the nodes in the following order: left subtree, root node, and right subtree.
main Function: We manually create nodes and link them to build a binary tree. Then, we call the inorder function to print the tree's nodes in inorder.

Binary Search Tree (BST) Example

A binary search tree is a special kind of binary tree where each node satisfies the following conditions:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
The left and right subtree each must also be a binary search tree.

Step 1: Insertion into a BST

Let's create a BST and write a function to insert elements into it.

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

// Define the structure for a single node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return node;
}

// Function to insert a new node with given data in a BST
struct Node* insert(struct Node* root, int data) {
    // If the tree is empty, return a new node
    if (root == NULL) {
        return newNode(data);
    }

    // Otherwise, recur down the tree
    if (data < root->data) {
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        root->right = insert(root->right, data);
    }

    // Return the unchanged node pointer
    return root;
}

// Function to perform inorder traversal of a BST
void inorder(struct Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(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);

    // Print inorder traversal of the BST
    printf("Inorder traversal of the BST: ");
    inorder(root);
    printf("\n");

    return 0;
}

Explanation:

insert Function: This function inserts a new node with the provided data into the BST. It recursively finds the correct position for the node based on BST properties.
main Function: We start with an empty tree (root = NULL) and use the insert function to add several values into the BST. We then call inorder to print the nodes in sorted order.

Step 2: Searching in a BST

Next, let's implement a search function to find a node in the BST.

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

// Define the structure for a single node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return node;
}

// Function to insert a new node with given data in a BST
struct Node* insert(struct Node* root, int data) {
    // If the tree is empty, return a new node
    if (root == NULL) {
        return newNode(data);
    }

    // Otherwise, recur down the tree
    if (data < root->data) {
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        root->right = insert(root->right, data);
    }

    // Return the unchanged node pointer
    return root;
}

// Function to search a given data in a BST
struct Node* search(struct Node* root, int data) {
    // Base case: root is null or data is present at root
    if (root == NULL || root->data == data)
        return root;

    // Data is greater than root's data
    if (root->data < data)
        return search(root->right, data);

    // Data is smaller than root's data
    return search(root->left, 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);

    // Search for a value in the BST
    int value = 40;
    struct Node* result = search(root, value);
    
    if (result != NULL) {
        printf("%d is found in the BST.\n", value);
    } else {
        printf("%d is not found in the BST.\n", value);
    }

    return 0;
}

Explanation:

search Function: This function searches for a node containing the specified data in the BST. It recurs down the tree based on BST properties.
main Function: We insert elements into the BST and then search for a specific value (40) using the search function.

Step 3: Deletion from a BST

Finally, let's implement a deletion function that removes a node from the BST.

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

// Define the structure for a single node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return node;
}

// Function to find the minimum value node in a BST
struct Node* minValueNode(struct Node* node) {
    struct Node* current = node;

    // Loop down to find the leftmost leaf
    while (current && current->left != NULL)
        current = current->left;

    return current;
}

// Function to delete a given data from a BST
struct Node* deleteNode(struct Node* root, int data) {
    // Base case: if root is NULL
    if (root == NULL)
        return root;

    // Recur down the tree
    if (data < root->data)
        root->left = deleteNode(root->left, data);
    else if (data > root->data)
        root->right = deleteNode(root->right, data);
    else {
        // Node with only one child or no child
        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;
        }

        // Node with two children. Get the inorder successor (smallest in the right subtree)
        struct Node* temp = minValueNode(root->right);

        // Copy the inorder successor's content to this node
        root->data = temp->data;

        // Delete the inorder successor
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

// Function to insert a new node with given data in a BST
struct Node* insert(struct Node* root, int data) {
    // If the tree is empty, return a new node
    if (root == NULL)
        return newNode(data);

    // Otherwise, recur down the tree
    if (data < root->data)
        root->left = insert(root->left, data);
    else if (data > root->data)
        root->right = insert(root->right, data);

    // Return the unchanged node pointer
    return root;
}

// Function to perform inorder traversal of a BST
void inorder(struct Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(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);

    // Print inorder traversal of the BST
    printf("Inorder traversal of the BST after insertion: ");
    inorder(root);
    printf("\n");

    // Delete a value from the BST
    int value = 40;
    root = deleteNode(root, value);

    // Print inorder traversal of the BST after deletion
    printf("Inorder traversal of the BST after deleting %d: ", value);
    inorder(root);
    printf("\n");

    return 0;
}

Explanation:

minValueNode Function: This function finds the node with the smallest value in a given subtree. It is useful for finding the inorder successor during deletion.
deleteNode Function: This function deletes a node with the specified data from the BST. It handles three cases: node with no children, node with one child, and node with two children.
main Function: We insert elements into the BST, delete a specific value (40), and then print the tree’s nodes in inorder before and after the deletion.

Summary

To handle binary trees, you need a structure defined for each node that includes pointers to left and right children.
You can insert data into a binary search tree by ensuring each element is placed according to BST properties.
To search for a node, you traverse the tree using comparisons between the target data and the current node’s data.
Deleting a node from a BST involves different scenarios depending on whether the node has zero, one, or two children.

Top 10 Interview Questions & 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. Each node in the tree has a value, and there is a single node at the top, called the root. The children of the root form a subtree and so on.

2. What is the difference between a Binary Tree and a Binary Search Tree (BST)?

Answer:

Binary Tree: A general tree data structure in which each node can have at most two children. There is no specific rule about the order of the values in the nodes.
Binary Search Tree (BST): A specific type of binary tree where for each node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater than the node's value. This property makes BSTs efficient for operations like searching, insertion, and deletion.

3. How do you insert a new element into a Binary Search Tree (BST)?

Answer:
To insert a new element into a BST:

Start at the root.
If the tree is empty, the new element becomes the root.
Compare the new element with the current node:
- If it’s smaller, move to the left child. Repeat the process until you find an empty left child and insert the new element there.
- If it’s larger, move to the right child. Repeat the process until you find an empty right child and insert the new element there.

4. How do you find the Inorder Traversal of a Binary Search Tree?

Answer:
Inorder traversal of a BST visits nodes in ascending order. The steps are:

Recursively traverse the left subtree.
Visit the root node.
Recursively traverse the right subtree.

5. How do you find the height of a Binary Tree?

Answer:
The height of a binary tree is the maximum number of edges from the root node to the farthest leaf node. The height can be computed recursively:

If the tree is empty, the height is -1.
Otherwise, compute the height of the left and right subtrees and add 1 to the greater of the two values.

6. What is the difference between a full binary tree and a complete binary tree?

Answer:

Full Binary Tree: A binary tree where every node has either 0 or 2 children.
Complete Binary Tree: A binary tree in which all levels are completely filled except possibly the last level, which is filled from left to right.

7. How do you find the minimum value in a BST?

Answer:
The minimum value in a BST is found by traversing the left child of each node starting from the root, until you reach a node that has no left child. The value of this node is the minimum.

8. How do you perform deletion in a Binary Search Tree?

Answer:
To delete a node from a BST:

Case 1: Node to be deleted is a leaf (no children): Simply remove the node.
Case 2: Node has one child: Replace the node with its child.
Case 3: Node has two children: Find the node's in-order successor (smallest node in the right subtree), copy the successor's value to the node, and delete the successor.

9. What is a balanced binary tree?

Answer:
A balanced binary tree is a binary tree where the difference in height between the left and right subtrees of any node is at most one. This ensures that the tree remains approximately the same height, which optimizes search, insert, and delete operations.

10. Can a binary tree be constructed from the given inorder and postorder traversal?

Answer:
Yes, a binary tree can be constructed from given inorder and postorder traversals. The last element in the postorder traversal is the root of the tree. Using this, you can find the root in the inorder traversal and then construct the left and right subtrees recursively.

C Programming Data Structures Binary Trees And Binary Search Trees Bst Complete Guide