Binary Search Tree (BST): Complete Guide with Implementation, Traversals & Searching

Introduction to Binary Search Tree (BST)
Objective of the Lab
Learning Outcomes
What is a Binary Search Tree?
Properties of BST
BST vs Binary Tree
Structure of a BST Node
BST Operations
- Insertion
- Searching
BST Traversal Algorithms
- PreOrder Traversal
- InOrder Traversal
- PostOrder Traversal
Real-World Example of BST
Time Complexity Analysis
Advantages & Disadvantages
Conclusion
FAQs

1. Introduction to Binary Search Tree (BST)

A Binary Search Tree (BST) is one of the most important data structures in computer science, widely used for efficient searching, sorting, and data organization.

It is a specialized form of a Binary Tree that follows a specific ordering rule, making operations faster and more optimized.

2. Objective of the Lab

The main objective of this lab is to:

Understand the concept of Binary Search Tree (BST)
Learn how to implement BST using programming
Perform traversal operations
Implement efficient searching techniques

3. Learning Outcomes

After completing this lab, students will be able to:

Code a BST as a special case of a Binary Tree
Implement traversal techniques:
- PreOrder
- InOrder
- PostOrder
Perform efficient searching in BST

. What is a Binary Search Tree?

A Binary Search Tree (BST) is a binary tree where each node follows this rule:

Left subtree contains values smaller than the node
Right subtree contains values greater than the node

5. Properties of BST

Each node has at most two children
Left child < Parent < Right child
No duplicate values (in standard BST)
InOrder traversal always gives sorted output

6. BST vs Binary Tree

Feature	Binary Tree	Binary Search Tree
Structure	Any arrangement	Ordered structure
Searching	O(n)	O(log n) (average)
Traversal	Not sorted	InOrder is sorted

7. Structure of a BST Node

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

8. BST Operations

A. Insertion in BST

Node* insert(Node* root, int value) {
    if (root == NULL) {
        return new Node{value, NULL, NULL};
    }

    if (value < root->data)
        root->left = insert(root->left, value);
    else if (value > root->data)
        root->right = insert(root->right, value);

    return root;
}

B. Searching in BST

Searching is efficient because of the ordered structure.

bool search(Node* root, int key) {
    if (root == NULL) return false;

    if (root->data == key)
        return true;
    else if (key < root->data)
        return search(root->left, key);
    else
        return search(root->right, key);
}

COMPLETE CODE:

#include <iostream>
using namespace std;

// Node structure
struct Node {
   int data;
   Node* left;
   Node* right;

Node(int value) {
    data = value;
    left = right = NULL;
}
};

// Insert function
Node* insert(Node* root, int value) {
    if (root == NULL) {
        return new Node(value);
    }

    if (value < root->data) {
        root->left = insert(root->left, value);
    }
    else if (value > root->data) {
        root->right = insert(root->right, value);
    }

    return root;
}

// Search function
bool search(Node* root, int key) {
    if (root == NULL) {
        return false;
    }

    if (root->data == key) {
        return true;
    }
    else if (key < root->data) {
        return search(root->left, key);
    }
    else {
        return search(root->right, key);
    }
}

// InOrder Traversal (for testing - prints sorted values)
void inorder(Node* root) {
    if (root == NULL) return;

    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

// Main function
int main() {
    Node* root = NULL;

    // Inserting values into BST
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    insert(root, 20);
    insert(root, 40);
    insert(root, 60);
    insert(root, 80);

    // Display BST (InOrder Traversal)
    cout << "BST InOrder Traversal (Sorted): ";
    inorder(root);
    cout << endl;

    // Searching values
    int key;
    cout << "Enter value to search: ";
    cin >> key;

    if (search(root, key)) {
        cout << "Value found in BST." << endl;
    } else {
        cout << "Value NOT found in BST." << endl;
    }

    return 0;
}

Output:

BST InOrder Traversal (Sorted): 20 30 40 50 60 70 80
Enter value to search: 60
Value found in BST.

9. BST Traversal Algorithms

Traversal means visiting nodes in a specific order.

1. PreOrder Traversal (Root → Left → Right)

void preorder(Node* root) {
    if (root == NULL) return;
    cout << root->data << " ";
    preorder(root->left);
    preorder(root->right);
}

2. InOrder Traversal (Left → Root → Right)

👉 Key Insight: In BST, InOrder traversal gives sorted data

void inorder(Node* root) {
    if (root == NULL) return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

3. PostOrder Traversal (Left → Right → Root)

void postorder(Node* root) {
    if (root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->data << " ";
}

Complete BST Traversal Code (C++)

#include <iostream>
using namespace std;

// Node structure
struct Node {
    int data;
    Node* left;
    Node* right;

Node(int value) {
    data = value;
    left = right = NULL;
}
};

// Insert function to build BST
Node* insert(Node* root, int value) {
    if (root == NULL) {
        return new Node(value);
    }

    if (value < root->data)
        root->left = insert(root->left, value);
    else if (value > root->data)
        root->right = insert(root->right, value);

    return root;
}

// PreOrder Traversal (Root → Left → Right)
void preorder(Node* root) {
    if (root == NULL) return;

    cout << root->data << " ";
    preorder(root->left);
    preorder(root->right);
}

// InOrder Traversal (Left → Root → Right)
void inorder(Node* root) {
    if (root == NULL) return;

    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

// PostOrder Traversal (Left → Right → Root)
void postorder(Node* root) {
    if (root == NULL) return;

    postorder(root->left);
    postorder(root->right);
    cout << root->data << " ";
}

// Main function
int main() {
    Node* root = NULL;

    // Insert values into BST
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    insert(root, 20);
    insert(root, 40);
    insert(root, 60);
    insert(root, 80);

    // Traversals
    cout << "PreOrder Traversal: ";
    preorder(root);
    cout << endl;

    cout << "InOrder Traversal: ";
    inorder(root);
    cout << endl;

    cout << "PostOrder Traversal: ";
    postorder(root);
    cout << endl;

    return 0;
}

10. Real-World Example of BST

Library Management System

Imagine a digital library system where books are stored using ISBN numbers.

Each book is inserted into the BST
Searching a book becomes fast using BST rules

Example Flow:

Insert books: 50, 30, 70, 20, 40
Search for book with ISBN 40
- Compare with root (50) → go left
- Compare with 30 → go right
- Found at 40

Why BST?

Fast lookup
Organized storage
Efficient updates

11. Time Complexity Analysis

Operation	Average Case	Worst Case
Insertion	O(log n)	O(n)
Searching	O(log n)	O(n)
Traversal	O(n)	O(n)

👉 Worst case occurs when BST becomes skewed (like a linked list)

12. Advantages & Disadvantages

✅ Advantages:

Efficient searching and insertion
Maintains sorted data
Easy to implement

❌ Disadvantages:

Can become unbalanced
Performance degrades in worst case
Requires extra memory for pointers

Activity 01:

Iterative BST Insertion Code (C++)

#include <iostream>
using namespace std;

// Node structure
struct Node {
   int data;
   Node* left;
   Node* right;

Node(int value) {
    data = value;
    left = right = NULL;
}
};

// Iterative Insert Function
Node* insertIterative(Node* root, int value) {
    Node* newNode = new Node(value);

    // If tree is empty
    if (root == NULL) {
        return newNode;
    }

    Node* current = root;
    Node* parent = NULL;

    while (current != NULL) {
        parent = current;

        if (value < current->data) {
            current = current->left;
        }
        else if (value > current->data) {
            current = current->right;
        }
        else {
            // Duplicate values not allowed
            return root;
        }
    }

    // Attach new node to the correct parent
    if (value < parent->data) {
        parent->left = newNode;
    } else {
        parent->right = newNode;
    }

    return root;
}

// InOrder Traversal (to verify BST)
void inorder(Node* root) {
    if (root == NULL) return;

    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

// Main function
int main() {
    Node* root = NULL;

    // Iterative Insertions
    root = insertIterative(root, 50);
    insertIterative(root, 30);
    insertIterative(root, 70);
    insertIterative(root, 20);
    insertIterative(root, 40);
    insertIterative(root, 60);
    insertIterative(root, 80);

    // Display tree
    cout << "InOrder Traversal (Sorted): ";
    inorder(root);
    cout << endl;

    return 0;
}

Output:

InOrder Traversal (Sorted): 20 30 40 50 60 70 80

Activity 02:

BST Traversals Code (PreOrder, InOrder, PostOrder)

#include <iostream>
using namespace std;

// Node structure
struct Node {
   int data;
   Node* left;
   Node* right;

Node(int value) {
    data = value;
    left = right = NULL;
}
};

// Iterative Insertion
Node* insertIterative(Node* root, int value) {
    Node* newNode = new Node(value);

    if (root == NULL) {
        return newNode;
    }

    Node* current = root;
    Node* parent = NULL;

    while (current != NULL) {
        parent = current;

        if (value < current->data)
            current = current->left;
        else if (value > current->data)
            current = current->right;
        else
            return root; // no duplicates
    }

    if (value < parent->data)
        parent->left = newNode;
    else
        parent->right = newNode;

    return root;
}

// PreOrder Traversal (Root → Left → Right)
void preorder(Node* root) {
    if (root == NULL) return;

    cout << root->data << " ";
    preorder(root->left);
    preorder(root->right);
}

// InOrder Traversal (Left → Root → Right)
void inorder(Node* root) {
    if (root == NULL) return;

    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

// PostOrder Traversal (Left → Right → Root)
void postorder(Node* root) {
    if (root == NULL) return;

    postorder(root->left);
    postorder(root->right);
    cout << root->data << " ";
}

// Main Function
int main() {
    Node* root = NULL;

    // Insert values
    root = insertIterative(root, 50);
    insertIterative(root, 30);
    insertIterative(root, 70);
    insertIterative(root, 20);
    insertIterative(root, 40);
    insertIterative(root, 60);
    insertIterative(root, 80);

    // Traversals
    cout << "PreOrder Traversal: ";
    preorder(root);
    cout << endl;

    cout << "InOrder Traversal: ";
    inorder(root);
    cout << endl;

    cout << "PostOrder Traversal: ";
    postorder(root);
    cout << endl;

    return 0;
}

Output:

PreOrder Traversal: 50 30 20 40 70 60 80
InOrder Traversal: 20 30 40 50 60 70 80
PostOrder Traversal: 20 40 30 60 80 70 50

Activity 03:

Write down the search method for BST.

1. Recursive Search Method in BST

bool search(Node* root, int key) {
    // Base case: empty tree or value found
    if (root == NULL)
        return false;

    if (root->data == key)
        return true;

    // Search in left subtree
    if (key < root->data)
        return search(root->left, key);

    // Search in right subtree
    return search(root->right, key);
}

2. Iterative Search Method in BST

bool searchIterative(Node* root, int key) {
    Node* current = root;

    while (current != NULL) {
        if (current->data == key)
            return true;
        else if (key < current->data)
            current = current->left;
        else
            current = current->right;
    }

    return false; // Not found
}

Activity 04:

Write down the method to count to number of nodes and find the sum of all nodes

#include <iostream>
using namespace std;

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

Node(int value) {
    data = value;
    left = right = NULL;
}
};

Node* insert(Node* root, int value) {
    if (root == NULL)
        return new Node(value);

    if (value < root->data)
        root->left = insert(root->left, value);
    else if (value > root->data)
        root->right = insert(root->right, value);

    return root;
}

int countNodes(Node* root) {
    if (root == NULL)
        return 0;

    return 1 + countNodes(root->left) + countNodes(root->right);
}

int sumNodes(Node* root) {
    if (root == NULL)
        return 0;

    return root->data + sumNodes(root->left) + sumNodes(root->right);
}

int main() {
    Node* root = NULL;

    // Insert values
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    insert(root, 20);
    insert(root, 40);
    insert(root, 60);
    insert(root, 80);

    cout << "Total Nodes: " << countNodes(root) << endl;
    cout << "Sum of Nodes: " << sumNodes(root) << endl;

    return 0;
}

Output:

Total Nodes: 7
Sum of Nodes: 350

3) Graded Lab Tasks

Lab Task 1

Implement the methods for Tree Traversal with Right Branch Priority i.e. Pre Order (NRL), Post Order (RLN) and In Order (RNL).

Lab Task 2

Write down code to print and count Leaf nodes of a BST.

Lab Task 3

Introduce method to delete a Node from BST, keep in mind that there are 3 possiblities for deletion, Node without any child, Node with One child and Node with both the children.

13. Conclusion

A Binary Search Tree (BST) is a powerful data structure that significantly improves search efficiency compared to linear structures.

By mastering:

BST implementation
Traversal algorithms
Searching techniques

you build a strong foundation for advanced topics like:

AVL Trees
Red-Black Trees
Heaps

14. FAQs

Q1: Why is BST faster than a normal binary tree?

Because it follows an ordered structure that reduces search space.

Q2: What traversal gives sorted output?

InOrder traversal

Q3: What is the biggest drawback of BST?

It can become unbalanced, leading to O(n) complexity.

DS LAB 07: Binary Search Tree (BST) Explained with Code, Traversals & Real-World Example

Write A Comment Cancel Reply

DS LAB 07: Binary Search Tree (BST) Explained with Code, Traversals & Real-World Example

Binary Search Tree (BST): Complete Guide with Implementation, Traversals & Searching

Table of Contents

1. Introduction to Binary Search Tree (BST)

2. Objective of the Lab

3. Learning Outcomes

. What is a Binary Search Tree?

5. Properties of BST

6. BST vs Binary Tree

7. Structure of a BST Node

8. BST Operations

A. Insertion in BST

B. Searching in BST

COMPLETE CODE:

Output:

9. BST Traversal Algorithms

1. PreOrder Traversal (Root → Left → Right)

2. InOrder Traversal (Left → Root → Right)

3. PostOrder Traversal (Left → Right → Root)

Complete BST Traversal Code (C++)

10. Real-World Example of BST

Library Management System

Example Flow:

Why BST?

11. Time Complexity Analysis

12. Advantages & Disadvantages

✅ Advantages:

❌ Disadvantages:

Activity 01:

Iterative BST Insertion Code (C++)

Activity 02:

Activity 03:

1. Recursive Search Method in BST

2. Iterative Search Method in BST

Activity 04:

Output:

3) Graded Lab Tasks

Lab Task 1

Lab Task 2

Lab Task 3

13. Conclusion

14. FAQs

Q1: Why is BST faster than a normal binary tree?

Q2: What traversal gives sorted output?

Q3: What is the biggest drawback of BST?

Related Posts

Lesson 14: Non-Linear Data Structures (Trees): Concepts, Terminology & Traversal Algorithms Explained

DS Theory Assignment 02: 5 Scenario-Based Problems on Stack, Queue, Priority Queue, and Deque

Lesson 12: Circular Queue and Priority Queue in Data Structures with C++ Implementation (Static & Dynamic)

DS LAB 06: Queue Data Structure in C++ with Real-Time Examples | Enqueue, Dequeue, Front & Rear Explained

Write A Comment Cancel Reply