I. Introduction to Data Structures

A. Data Structures:

Computer programming uses building elements called data structures. They assist us in intelligently organizing and storing data. This makes working with the data by programmers simple. Data structures come in a variety of forms, including trees, linked lists, and arrays. Each kind is useful for various duties and helps with various issues.

B. Importance of Data Structures in Programming:

Data structures play a crucial role in programming for several reasons. Firstly, they allow programmers to optimize the use of memory, making data storage more efficient. Secondly, data structures facilitate the implementation of algorithms, making it easier to perform various operations like searching, sorting, and inserting data. Smart data storage techniques can significantly improve a program's performance. The software might operate more quickly and require less processing power as a result. As a result, understanding and effectively implementing data structures are essential skills for any programmer aiming to write robust and efficient code.

C. Linked Lists and Binary Search Trees: Two essential data structures: Linked Lists and Binary Search Trees.

Linked Lists: A linked list resembles a line of data blocks. Each block has information and a hint for the following block. The final block is clueless and indicates the end. There are various kinds, including lists that only move in one direction, lists that go both ways, and lists that loop.

Singly Linked List: Each node holds data and points to the next one.

Doubly Linked List: Each node has data and two references. The first pointer points to the node after it, and the second one points to the node before it.

Circular Linked List: A closed loop is created in a circular linked list when the final node links back to the beginning node.

Linked lists can change their size as needed while the program is running. They are commonly used for scenarios where frequent insertions and deletions are required, as these operations can be performed efficiently in linked lists.

Binary Search Trees (BST): A binary search tree functions as a kind of family tree for numbers. It consists of nodes joined in unique ways, which makes up its structure. Each node is identified by a number, and it can have a maximum of two offspring. A smaller or equal number is displayed for one child on the left, and a larger number is displayed for the child on the right. We can rapidly locate, add, or remove numbers because to this set up's orderly structure. Due to their resemblance to ordered lists of numbers, binary search trees are frequently employed to locate objects quickly. They enable fast access to data, making them ideal for scenarios where quick searching is a requirement, such as database indexing and dictionary implementations.

II. Linked Lists

A.Introduction to Linked Lists:

A chain of items is analogous to a linked list. It contains a number of objects known as nodes. Linked lists can quickly adjust in size as opposed to arrays. A pointer that indicates where the next node is located, and the actual data are both present in each node of a linked list. The last node's pointer points to a blank space, indicating that it is the list's end.

1.Definition of a Linked List:

A linked list is a method for organizing data in computers. Each piece of information is contained in a box called a "node" and is organized like a chain. Each box not only contains information but also identifies the box after it. The first box is referred to as the "head," and the last box, which points in all directions, is referred to as the "tail." There are various forms of linked lists, including those where each box points ahead, those where boxes point both forward and backward, and even those that form a loop.

2.Nodes and Pointers in Linked Lists:

Nodes are like building blocks of a linked list. They have two parts: data and a pointer that shows where the next node is. Data holds the actual information, and the pointer points to the next node. This linking using pointers is what makes a linked list special compared to an array.

For instance, in a singly linked list, a node can be represented by a struct in C:

struct Node {

    int data;         

    struct Node* next; 

};

When a new node is added to a linked list, memory is dynamically allocated for the node using functions like “malloc ()” in C. The pointer in the previous node is then updated to point to the newly created node.

Example of a simple singly linked list with three nodes:

|  5   |  *--------->|  10  |  *--------->|  15  | NULL |

The first node contains the data ‘5’, and its ‘next’ pointer points to the second node, which contains the data ‘10’, and so on until the last node whose ‘next’ pointer is NULL, indicating the end of the linked list.

B. Singly Linked Lists

Data structures are fundamental building blocks in computer science, enabling efficient data organization and manipulation. One such essential data structure is the Singly Linked List. It consists of nodes connected in a straight line, each of which has data and a reference (pointer) to the node after it.

1.Explanation of Singly Linked List:

Single Linked Lists are a unique type of data organization that make adding and removing items simple. Each item of data is linked to the one before it in a chain-like fashion. In contrast to arrays, which demand a particular memory order, this does not. You can handle various data volumes in a linked list without concern. In a linked list, each item of data has two components: the actual value and a pointer to the item of data after it.

Imagine a chain of connected nodes, where the first node is called the head, and the last node's next pointer points to NULL, signifying the end of the list. The head serves as the starting point to access the entire list. If the list is empty, then the head is NULL.

Operations on Singly Linked Lists: Now, let's explore the fundamental operations you can perform on singly linked lists:

Insertion: Insertion in a singly linked list involves adding a new node at a specific position, either at the beginning, end, or any position within the list.

To add a new node at the start:
Make a new node.
Link it to the first node.
Make it the new first node.

Adding a Node at the End: To add a new node at the end of the list, do this:
Make a fresh node with the data you want.
Go through the list from the start to the final node.
Connect the last node's next spot to the new node.
Connect the new node's next spot to nothing, showing it's the end of the list.

C. Adding a Node in a Certain Spot: If you want to put a new thing in a certain place in a list, do this:

Make a fresh new thing with the information you want.
Go through the list until you find the old thing right before the spot where you want to put the new thing.
Change some pointers to stick the new thing into the spot where you want it.

Deletion: Deletion in a singly linked list involves removing a node from the list based on the given data or position.

Deletion by Value: To delete a node with a specific value, follow these steps:

Traverse the list to find the node with the given value.
Adjust the pointers to skip the node and connect its previous node to the next node.

Deletion by Position: To delete a node at a specific position, follow these steps:

Traverse the list to reach the node at the desired position.
Adjust the pointers to skip the node and connect its previous node to the next node.

Traversal: Traversal in a singly linked list involves visiting each node one by one, starting from the head, and performing some operation on its data.

To traverse a singly linked list, follow these steps:

Start from the head node.
Perform the desired operation on the data of the current node.
Move to the next node using the next pointer.
Repeat the process until you reach the end of the list (next pointer becomes NULL).

C. Doubly Linked Lists

Data structures are fundamental components of programming that allow us to organize and manage data efficiently. One such essential data structure is the Doubly Linked List.

1. Explanation of Doubly Linked List:

Each item of data is kept in a container referred to as a "node" in a doubly linked list. Each node contains two unique pointers: one that points to the box that comes after it in the line of boxes, and the other that points to the box that comes before it. Because of this unique configuration, you can navigate the boxes both forward and backward. Because of this, the term "doubly" linked is used.

The structure of a Doubly Linked List Node in C can be defined as follows:

struct Node {

    struct Node* prev;

    int data;

    struct Node* next;

};

2. Operations on Doubly Linked Lists:

Insertion: A Doubly Linked List can have items added in one of three places: at the beginning, at the end, or after a specific time.

Insertion at the Beginning: To insert a new node at the beginning of the Doubly Linked List, follow these steps:

void insertAtBeginning(struct Node** head, int data) {

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

    newNode->data = data;

    newNode->prev = NULL;

    newNode->next = (*head);

    if ((*head) != NULL) {

        (*head)->prev = newNode;

    }

    (*head) = newNode;

}

Insertion at the End: To insert a new node at the end of the Doubly Linked List, follow these steps:

void insertAtEnd(struct Node** head, int data) {

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

    newNode->data = data;

    newNode->next = NULL;

    if ((*head) == NULL) {

        newNode->prev = NULL;

        (*head) = newNode;

        return;

    }

    struct Node* lastNode = (*head);

    while (lastNode->next != NULL) {

        lastNode = lastNode->next;

    }

    lastNode->next = newNode;

    newNode->prev = lastNode;

}

Insertion after a Specific Node: To insert a new node after a given node in the Doubly Linked List, follow these steps:

void insertAfter(struct Node* prevNode, int data) {

    if (prevNode == NULL) {

        printf("Previous node cannot be NULL.");

        return;

    }

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

    newNode->data = data;

    newNode->next = prevNode->next;

    prevNode->next = newNode;

    newNode->prev = prevNode;

    if (newNode->next != NULL) {

        newNode->next->prev = newNode;

    }

}

Deletion:

Deletion in a Doubly Linked List can be performed for the first occurrence of a given key or for a specific node.

Deletion by Key: To delete the first occurrence of a node with a specific key in the Doubly Linked List, follow these steps:

void deleteByKey(struct Node** head, int key) {

    struct Node* temp = (*head);

    while (temp != NULL && temp->data != key) {

        temp = temp->next;

    }

    if (temp == NULL) {

        printf("Node with key %d not found.", key);

        return;

    }

    if (temp->prev != NULL) {

        temp->prev->next = temp->next;

    } else {

        (*head) = temp->next;

    }

    if (temp->next != NULL) {

        temp->next->prev = temp->prev;

    }

    free(temp);

}

Deletion of Specific Node: To delete a given node in the Doubly Linked List, follow these steps:

void deleteNode(struct Node** head, struct Node* delNode) {

    if ((*head) == NULL || delNode == NULL) {

        return;

    }

    if ((*head) == delNode) {

        (*head) = delNode->next;

    }

    if (delNode->next != NULL) {

        delNode->next->prev = delNode->prev;

    }

    if (delNode->prev != NULL) {

        delNode->prev->next = delNode->next;

    }

    free(delNode);

}

Traversal: To traverse a Doubly Linked List, we can move either from the beginning to the end or from the end to the beginning. Here's an example of forward traversal:

void printList(struct Node* node) {

    while (node != NULL) {

        printf("%d ", node->data);

        node = node->next;

    }

    printf("\n");

}

D. Circular Linked Lists

1.Explanation of Circular Linked List:

A unique form of linked list called a circular linked list has the last node looping back around to connect to the initial node. A circular linked list's last node points back to the beginning node while a standard linked list's last node points to nothing (NULL). It is simple to navigate between any node in the list because to the looped structure.

Unlike linear linked lists, circular linked lists do not have a NULL pointer at the end, making them advantageous for certain applications. Circular linked lists can be implemented using a struct in C that contains the data to be stored and a pointer to the next node in the list.

2.Operations on Circular Linked Lists (Insertion, Deletion, Traversal):

a.Insertion in a Circular List:

Start: Make a new node, link it to the first one, and update the last node to point to it.
End: Make a new node, connect the last node to it, then link the new node back to the first.
Middle: Go to the desired spot, adjust links to fit the new node.

b.Deletion from a Circular List:

Start: Link the last node to the second node and remove the first one.
End: Connect the second-last node to the first and remove the last one.
Middle: Find the node, update the previous node's link to skip it, then remove it.

c.Traversing the List:

Move from the first node to the next and keep going until you're back at the start. You can loop or use recursion for this.

Pros and Cons of Linked Lists

1.Advantages of Linked Lists

a. Dynamic Size: Linked lists can change in size while the program is running, getting bigger or smaller as the computer gives or takes away memory. This flexibility is particularly useful when the size of the data structure varies over time.

b. Efficient Insertions and Deletions: Insertions and deletions in linked lists can be efficient, especially for singly linked lists when performed at the beginning or the end. You just have to change the pointers, and there's no need to move the things around.

c. Memory Allocation: Linked lists use memory efficiently. Unlike arrays, where memory must be allocated in advance, linked lists only use memory for the actual data and the pointers to the next nodes.

d. No Wasted Memory: Linked lists avoid the "memory wastage" problem that can occur with arrays, where you may need to allocate extra memory to accommodate potential growth.

2.Disadvantages of Linked Lists

a. Sequential Access: Unlike arrays, linked lists do not provide direct or random access to elements. Traversing the list sequentially is necessary to access specific elements.

b. Extra Memory Overhead: Linked lists require extra memory to store the pointers, which can lead to increased memory overhead compared to arrays.

c. Lack of Cache Locality: Linked list elements are scattered throughout the memory, which can result in cache misses and slower access times compared to contiguous memory used in arrays.

d. More Complex Implementation: Implementing linked lists can be more intricate than arrays, especially handling pointer manipulations and edge cases like handling circular references.

III. Binary Search Trees (BST)

A. Introduction to Binary Search Trees

A Binary Search Tree (BST) is a crucial concept in computer science. It's a unique variety of binary tree with the following rule: for every dot in the tree, all dots on its left side have smaller values, and all dots on its right side have bigger values. This rule makes it easier to search, add, and remove data fast.

Characteristics of BST:

Binary Search Trees possess several key characteristics that make them valuable in various applications:

a. Sorted Structure: As mentioned earlier, BSTs maintain their elements in a sorted order, facilitating faster searching and retrieval of data.

b. Recursive Nature: The BST is a recursive data structure, with each node potentially having its own left and right subtrees, each of which is also a BST.

c. Unique Values: In a typical implementation, BSTs do not allow duplicate values, ensuring unique elements are stored within the tree.

d. Balanced vs. Unbalanced BSTs: Depending on the order of insertion or deletion of nodes, a BST can become either balanced (where the height is minimized) or unbalanced (where the height becomes skewed, leading to suboptimal performance).

B. Building a BST

Binary Search Trees (BST) are a type of binary tree data structure that maintains a sorted order of elements. Each node in the tree has at most two children, a left child, and a right child. The ordering rule in a BST state that for every node:

All elements in the left subtree are less than the node's value.
All elements in the right subtree are greater than the node's value.

To implement a BST in C, you would need to define a structure for the nodes that would include at least two fields: one for storing the value of the node and two pointers for the left and right children.

struct TreeNode {

    int data;

    struct TreeNode* left;

    struct TreeNode* right;

};

With this structure, you can create functions to perform various operations on the BST:

1.Creating a new node:

struct TreeNode* createNode(int value) {

    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));

    newNode -> data = value;

    newNode -> left = NULL;

    newNode -> right = NULL;

    return newNode;

}

2.Insertion Operation in BST: The insertion operation in a BST involves comparing the new element with the current node's value. If it's smaller, move to the left subtree; if larger, move to the right subtree. If the subtree is empty, create a new node and attach it as the left or right child. Repeat the process until the new element finds its correct position in the tree.

struct TreeNode* insert(struct TreeNode* root, int value) {

if (root == NULL) {

        return createNode(value);

    }

    if (value < root -> data) {

        root -> left = insert(root -> left, value);

    } else if (value > root -> data) {

        root -> right = insert(root -> right, value);

    }

    return root;

}

3.Deletion Operation in BST: Removing nodes from a Binary Search Tree while preserving its ordering property requires careful consideration of different cases. The deletion operation follows these steps:

a. Search for the node to be deleted.

b. If it has no children (a leaf node), remove it directly.

c. If it has one child, link its parent to the child, bypassing the node to be deleted.

d. If it has two children, find its successor (right subtree) or predecessor (left subtree).

e. Replace the node with its successor/predecessor and recursively delete it from its original position.

struct TreeNode* findMin(struct TreeNode* node) {

    while (node->left != NULL) {

        node = node->left;

    }

    return node;

}

struct TreeNode* deleteNode (struct TreeNode* root, int value) {

    if (root == NULL) {

        return root;

    }

    if (value < root -> data) {

        root -> left = deleteNode (root->left, value);

    } else if (value > root -> data) {

        root -> right = deleteNode (root -> right, value);

    } 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 = findMin(root -> right);

        root -> data = temp->data;

        root -> right = deleteNode (root -> right, temp -> data);

    }

    return root;

}

C. Traversing a BST:

Inorder Traversal: Inorder traversal is a method used to visit nodes in a BST in a specific order. In this traversal, we first visit the left subtree, then the current node, and finally the right subtree. This results in a sorted order output for BSTs since the left subtree always contains smaller elements, and the right subtree contains larger elements than the current node.

The recursive implementation of inorder traversal in C can be achieved as follows:

void inorderTraversal(Node* root) {

    if (root != NULL) {

        inorderTraversal(root->left);

        printf("%d ", root->data);

        inorderTraversal(root->right);

    }

}

Preorder Traversal: Preorder traversal is another way to visit nodes in a BST. This method of traversing a tree involves starting at the current location, then looking at the left side of the tree, and finally the right side. Preorder traversal comes in handy when replicating a math tree or creating the first component of an expression from it.

The recursive implementation of preorder traversal in C can be achieved as follows:

void preorderTraversal(Node* root) {

    if (root != NULL) {

        printf("%d ", root->data);

        preorderTraversal(root->left);

        preorderTraversal(root->right);

    }

}

Postorder Traversal: Postorder traversal visits the nodes in a BST in the order of left subtree, right subtree, and then the current node. Since it ensures that child portions are eliminated before their parent parts, this method of advancing through the tree is frequently used to remove the entire tree.

The recursive implementation of postorder traversal in C can be achieved as follows:

void postorderTraversal(Node* root) {

    if (root != NULL) {

        postorderTraversal(root->left);

        postorderTraversal(root->right);

        printf("%d ", root->data);

    }

}

D. Searching in BST:

Recursive Search: A recursive search is a straightforward approach to finding a specific element in a BST. Depending on whether the item we're looking for is bigger or smaller than what's in the present stop, we begin our search from the focal point and move to the left or right side.

The recursive search function in C can be implemented as follows:

Node* recursiveSearch(Node* root, int key) {

    if (root == NULL || root->data == key)

        return root;

    if (key < root->data)

        return recursiveSearch(root->left, key);

    return recursiveSearch(root->right, key);

}

Iterative Search: Iterative search provides an alternative method to find an element in a BST without using recursion. This entails moving through the tree one node at a time until you reach the desired node. The iterative search function in C can be implemented as follows:

Node* iterativeSearch(Node* root, int key) {

    while (root != NULL && root->data != key) {

        if (key < root->data)

            root = root->left;

        else

            root = root->right;

    }

    return root;

}

E. Balancing BSTs (Brief mention of AVL or Red-Black Trees):

Balancing BSTs is crucial to maintain their efficiency during operations. Unbalanced trees can lead to skewed structures, resulting in poor performance. Two common methods to balance BSTs are AVL trees and Red-Black trees.

AVL Trees: AVL trees are unique binary search trees with constant height balance. By measuring the lengths of its left and right branches, each node's balance is examined. The height difference should only be -1, 0 or 1. Rotations are used to restore the tree's balance if this rule is breached.
Red-Black Trees: Self-balancing binary search trees also come in the form of red-black trees. In a Red-Black tree, each node is given one of two colors: red or black. The tree upholds five characteristics that guarantee its balance across insertions and deletions.

IV. Implementation of Linked Lists and BST in C

A. Defining Structures for Nodes

Before we delve into the implementation of linked lists and binary search trees (BST) in C, it is essential to understand the fundamental concept of nodes. These data structures' fundamental building unit, the node, has two main components: data and a pointer. The data field holds the actual information we want to store, while the pointer field points to the next node in the linked list or the left and right children in a binary search tree.

In C, we can define a basic structure for a node as follows:

struct Node {

    int data;         

    struct Node* next;

    struct Node* left;

    struct Node* right;

};

B. Creating Functions for Linked Lists

Insertion Function: Insertion is a fundamental operation in linked lists, allowing us to add new elements to the data structure. The process involves creating a new node with the given data and appropriately updating the pointers to maintain the integrity of the linked list.

void insert(struct Node** head, int data) {

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

    if (newNode == NULL) {

        // Memory allocation failed

        return;

    }

    newNode->data = data;

    newNode->next = *head;

    *head = newNode;

}

2.Deletion Function: The deletion function allows us to remove elements from a Linked List. For this, we need to consider various cases, including deleting the head node, intermediate nodes, and the last node. Let's see the C code for a simple Linked List deletion function:

#include <stdio.h>

#include <stdlib.h>

struct Node {

    int data;

    struct Node* next;

};

void deleteNode(struct Node** head, int key) {

    struct Node* temp = *head;

    struct Node* prev = NULL;

    if (temp != NULL && temp->data == key) {

        *head = temp->next;

        free(temp);

        return;

    }

    while (temp != NULL && temp->data != key) {

        prev = temp;

        temp = temp->next;

    }

    // Key not found in the Linked List

    if (temp == NULL) {

        printf("Key not found in the Linked List.\n");

        return;

    }

    // Unlink the node containing the key

    prev->next = temp->next;

    free(temp);

}

3.Traversal Function: The traversal function is used to print or process all elements of the Linked List. Here's the C code for a simple traversal function:

void printLinkedList(struct Node* head) {

    struct Node* current = head;

    while (current != NULL) {

        printf("%d -> ", current->data);

        current = current->next;

    }

    printf("NULL\n");

}

C. Creating Functions for Binary Search Trees:

Insertion Function: The insertion function allows us to add elements to a Binary Search Tree while maintaining its properties, where elements to the left are less than the root, and elements to the right are greater. Here's the C code for a simple insertion function:

struct TreeNode {

    int data;

    struct TreeNode* left;

    struct TreeNode* right;

};

struct TreeNode* insertNode(struct TreeNode* root, int key) {

    if (root == NULL) {

        struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));

        newNode->data = key;

        newNode->left = newNode->right = NULL;

        return newNode;

    }

    if (key < root->data) {

        root->left = insertNode(root->left, key);

    } else if (key > root->data) {

        root->right = insertNode(root->right, key);

    }

    return root;

}

2.Deletion Function: The deletion function for a Binary Search Tree removes a specified element while preserving the BST properties. Handling all the cases of deletion (no children, one child, two children) requires a bit more complexity than the insertion operation. Here's the C code for a simple deletion function:

struct TreeNode* findMin(struct TreeNode* node) {

    while (node->left != NULL) {

        node = node->left;

    }

    return node;

}

struct TreeNode* deleteNode(struct TreeNode* root, int key) {

    if (root == NULL) {

        return root;

    }

    if (key < root->data) {

        root->left = deleteNode(root->left, key);

    } else if (key > root->data) {

        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 = findMin(root->right);

        root->data = temp->data;

        root->right = deleteNode(root->right, temp->data);

    }

    return root;

}

3.Traversal Function: Traversal in a Binary Search Tree allows us to visit all elements in a specific order, such as Inorder, Preorder, or Postorder. Let's look at the Inorder traversal function:

void inorderTraversal(struct TreeNode* root) {

    if (root != NULL) {

        inorderTraversal(root->left);

        printf("%d -> ", root->data);

        inorderTraversal(root->right);

    }

}

4.Searching Function: The searching function helps us determine if a specific element exists in the Binary Search Tree. Here's a simple search function:

struct TreeNode* search(struct TreeNode* root, int key) {

    if (root == NULL || root->data == key) {

        return root;

    }

    if (key < root->data) {

        return search(root->left, key);

    }

    return search(root->right, key);

}

D.Efficient C Implementation of Linked Lists and Binary Search Trees

1.Linked List Implementation:

#include <stdio.h>

#include <stdlib.h>

struct Node {

    int data;

    struct Node* next;

};

struct Node* createNode(int data) {

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

    newNode->data = data;

    newNode->next = NULL;

    return newNode;

}

struct Node* insert(struct Node* head, int data) {

    if (head == NULL) {

        return createNode(data);

    }

    head->next = insert(head->next, data);

    return head;

}

void printList(struct Node* head) {

    while (head != NULL) {

        printf("%d ", head->data);

        head = head->next;

    }

}

void freeList(struct Node* head) {

    while (head != NULL) {

        struct Node* temp = head;

        head = head->next;

        free(temp);

    }

}

int main() {

    struct Node* head = NULL;

    head = insert(head, 10);

    head = insert(head, 20);

    head = insert(head, 30);

    head = insert(head, 40);

    printf("Linked List: ");

    printList(head);

    freeList(head);

    return 0;

}

Output:

Linked List: 10 20 30 40

2.Binary Search Tree (BST) Implementation:

#include <stdio.h>

#include <stdlib.h>

struct TreeNode {

    int data;

    struct TreeNode* left;

    struct TreeNode* right;

};

struct TreeNode* createNode(int data) {

    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));

    newNode->data = data;

    newNode->left = NULL;

    newNode->right = NULL;

    return newNode;

}

struct TreeNode* insert(struct TreeNode* 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;

}

void inorderTraversal(struct TreeNode* root) {

    if (root != NULL) {

        inorderTraversal(root->left);

        printf("%d ", root->data);

        inorderTraversal(root->right);

    }

}

void freeBST(struct TreeNode* root) {

    if (root != NULL) {

        freeBST(root->left);

        freeBST(root->right);

        free(root);

    }

}

int main() {

    struct TreeNode* root = NULL;

    root = insert(root, 50);

    root = insert(root, 30);

    root = insert(root, 20);

    root = insert(root, 40);

    root = insert(root, 70);

    root = insert(root, 60);

    root = insert(root, 80);

    printf("BST Inorder Traversal: ");

    inorderTraversal(root);

    freeBST(root);

    return 0;

}