Binary search tree

 Binary Search Tree (BST)

Aim

To implement a Binary Search Tree with create, search, and non-recursive traversals in C.

Operations in BST

  1. Create → Insert a node into BST.

  2. Search → Find whether an element exists in BST.

  3. Non-recursive Traversals

    • Inorder (Left, Root, Right)

    • Preorder (Root, Left, Right)

    • Postorder (Left, Right, Root)

Algorithm

Create (Insert):

  1. Create a new node.

  2. If tree empty → new node becomes root.

  3. Else, compare with root → go left if smaller, right if larger.

  4. Repeat until correct position found.

Search:

  1. Start at root.

  2. If key = root → found.

  3. If key < root → search left subtree.

  4. Else search right subtree.

  5. Repeat until found or NULL.

Non-Recursive Traversals:

  • Inorder: Use stack → push left nodes, visit root, then right.

  • Preorder: Use stack → push root, then right, then left.

  • Postorder: Use two stacks or modified stack logic.

Flowchart

Binary Tree Sort - Binary Search Tree Flow Chart Clipart - Large Size Png Image - PikPng

C Code – BST Implementation

#include <stdio.h>

#include <stdlib.h>

struct Node {

    int data;

    struct Node *left, *right;

};

// Create 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;

}

// Insert node in BST

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

    struct Node* newNode = createNode(data);

    struct Node* parent = NULL, *temp = root;

    while (temp != NULL) {

        parent = temp;

        if (data < temp->data)

            temp = temp->left;

        else

            temp = temp->right;

    }

    if (parent == NULL)  // Tree empty

        return newNode;

    else if (data < parent->data)

        parent->left = newNode;

    else

        parent->right = newNode;


    return root;

}

// Search element in BST

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

    while (root != NULL) {

        if (key == root->data)

            return root;

        else if (key < root->data)

            root = root->left;

        else

            root = root->right;

    }

    return NULL;

}

// Non-recursive Inorder Traversal

void inorder(struct Node* root) {

    struct Node* stack[100];

    int top = -1;

    struct Node* curr = root;

    while (curr != NULL || top != -1) {

        while (curr != NULL) {

            stack[++top] = curr;

            curr = curr->left;

        }

        curr = stack[top--];

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

        curr = curr->right;

    }

}


// Non-recursive Preorder Traversal

void preorder(struct Node* root) {

    if (root == NULL) return;

    struct Node* stack[100];

    int top = -1;

    stack[++top] = root;

    while (top != -1) {

        struct Node* node = stack[top--];

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


        if (node->right) stack[++top] = node->right;

        if (node->left) stack[++top] = node->left;

    }

}

// Non-recursive Postorder Traversal

void postorder(struct Node* root) {

    if (root == NULL) return;

    struct Node* stack1[100], *stack2[100];

    int top1 = -1, top2 = -1;

    stack1[++top1] = root;

    while (top1 != -1) {

        struct Node* node = stack1[top1--];

        stack2[++top2] = node;

        if (node->left) stack1[++top1] = node->left;

        if (node->right) stack1[++top1] = node->right;

    }

    while (top2 != -1) {

        struct Node* node = stack2[top2--];

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

    }

}

// Driver Program

int main() {

    struct Node* root = NULL;

    int choice, val, key;

    struct Node* result;

    while (1) {

        printf("\n--- BST Menu ---\n");

        printf("1. Insert\n");

        printf("2. Search\n");

        printf("3. Inorder Traversal (Non-Recursive)\n");

        printf("4. Preorder Traversal (Non-Recursive)\n");

        printf("5. Postorder Traversal (Non-Recursive)\n");

        printf("6. Exit\n");

        printf("Enter choice: ");

        scanf("%d", &choice);

        switch (choice) {

            case 1:

                printf("Enter value to insert: ");

                scanf("%d", &val);

                root = insert(root, val);

                break;

            case 2:

                printf("Enter value to search: ");

                scanf("%d", &key);

                result = search(root, key);

                if (result != NULL)

                    printf("Element %d found in BST.\n", key);

                else

                    printf("Element %d not found.\n", key);

                break;

            case 3:

                printf("Inorder Traversal: ");

                inorder(root);

                printf("\n");

                break;

            case 4:

                printf("Preorder Traversal: ");

                preorder(root);

                printf("\n");

                break;

            case 5:

                printf("Postorder Traversal: ");

                postorder(root);

                printf("\n");

                break;

            case 6:

                printf("Exiting...\n");

                exit(0);

            default:

                printf("Invalid choice!\n");

        }

    }

    return 0;

}

Comments

Post a Comment

Popular posts from this blog

Stack using array

Image
  1) Stack using Array Aim To implement stack operations (Push, Pop, Display) using arrays in C. Objective To study the LIFO (Last In, First Out) principle. To practice array-based implementation of data structures. Algorithm Push: If top == n-1, then overflow. Else top = top + 1 and insert element at stack[top]. Pop: If top == -1, then underflow. Else delete element from stack[top], then top = top - 1. Display: If top == -1, stack empty. Else print elements from stack[top] to stack[0]. Flowchart  C Code (Stack using Array) #include <stdio.h> #define MAX 5 int main() {     int stack[MAX], top = -1, choice, item, i;     while (1) {         printf("\n--- Stack Menu ---\n");         printf("1. Push\n2. Pop\n3. Display\n4. Exit\n");         printf("Enter choice: ");         scan...
Read more

Bubble Sort

Image
  2) Bubble Sort Aim To arrange elements in ascending order using Bubble Sort (without functions). Objective To study simple comparison-based sorting. To understand swapping of adjacent elements. Algorithm Input number of elements and array. Repeat for i = 0 to n-1 Repeat for j = 0 to n-i-2 If arr[j] > arr[j+1], swap them. Print sorted array. Flowchart C Code #include <stdio.h> int main() {     int n, i, j, temp;     printf("Enter number of elements: ");     scanf("%d", &n);     int arr[n];     printf("Enter array elements: ");     for (i = 0; i < n; i++)         scanf("%d", &arr[i]);     for (i = 0; i < n - 1; i++) {         for (j = 0; j < n - i - 1; j++) {             if (arr[j]...
Read more

Singly linked list implementation

Image
  Singly Linked List Implementation Aim To implement basic operations on a Singly Linked List in C. Objective To study dynamic memory allocation using linked lists. To perform Insert, Delete, Traverse operations. To understand pointer manipulation in data structures. Operations in Singly Linked List Insert at Beginning Insert at End Insert at Position Delete from Beginning Delete from End Delete from Position Display List Algorithm Insert at Beginning Create new node. new->next = head. head = new. Insert at End Create new node. If list empty → head = new. Else traverse to last node, set last->next = new. Insert at Position Traverse until position-1. Link new node in between. Delete from Beginning If empty → print "Underflow". Else move head to head->next, free old head. Delete from End If empty → print "Underflow". Else traverse to last-1 node, set last->next = NULL, free last. Delete from Position Traverse until position-1. Adjust links and free node...
Read more