Binary Search Tree BST Notes 2025 B.Tech/BCA with Operations and Diagrams

A Binary Search Tree (BST) is a special form of a binary tree in which the nodes are organized in a particular order. Each node in a BST contains a key such that all keys in the left subtree of a node are less than the node’s key, and all keys in the right subtree are greater. This hierarchical structure allows efficient searching, insertion, and deletion operations, making BSTs a fundamental structure in computer science.

Basic Structure of Binary Search Tree

A binary search tree is composed of nodes. Each node contains the following components: Data (Key), Left Child, Right Child. The left child node contains values smaller than the parent node, while the right child node contains values greater than the parent node.

📌 Insert Diagram: Basic BST Node Structure

Example BST:

       50
      /  \
    30    70
   / \    / \
  20 40  60 80

In the above BST:

Node 50 is the root.
Nodes 30 and 70 are the left and right children of 50 respectively.
Nodes 20, 40, 60, and 80 are the leaf nodes.

Properties of Binary Search Trees

Uniqueness: All nodes have unique keys.
Ordering: Left subtree keys < parent node key < right subtree keys.
Recursive Definition: A BST is recursively defined as a node with two children which are also BSTs.
Average Time Complexity: Search, Insert, and Delete operations have average time complexity of O(log n) in balanced BSTs.

Operations on Binary Search Trees

1. Insertion in BST

Insertion in a binary search tree is performed recursively or iteratively. Starting from the root, the new key is compared with the current node’s key. If smaller, move to the left child; if greater, move to the right child. This continues until a suitable leaf position is found.

Algorithm:

Step 1: Start at root node.
Step 2: Compare the key to be inserted with the root.
Step 3: If key < root, move to left subtree; if key > root, move to right subtree.
Step 4: Repeat until a null reference is found.
Step 5: Insert node at the null position.

Example: Insert 25 into the BST:

       50
      /  \
    30    70
   / \    / \
  20 40  60 80

Result after inserting 25:

       50
      /  \
    30    70
   / \    / \
  20 40  60 80
   \
   25

2. Searching in BST

Searching follows the same recursive path as insertion. If the key matches the node’s key, the search is successful. Otherwise, we traverse the left or right subtree based on the key comparison.

Time Complexity: O(h), where h is the height of the tree.

Worst-case: O(n), when tree becomes a skewed BST.

3. Deletion in BST

Deletion is more complex and categorized into three cases:

Case 1: Node to be deleted is a leaf node.
Case 2: Node has only one child.
Case 3: Node has two children.

Case 1 – Deleting a leaf node: Simply remove the node.

Case 2 – Node with one child: Replace the node with its child.

Case 3 – Node with two children: Find the inorder successor (smallest node in the right subtree), copy its value, and delete the successor.

Example: Delete 30 from BST:

       50
      /  \
    30    70
   / \    / \
  20 40  60 80

After deletion:

       50
      /  \
    40    70
   /     / \
  20    60 80

4. Inorder Traversal of BST

Inorder traversal visits nodes in left-root-right order. For BSTs, this returns keys in sorted order.

Example BST:

       50
      /  \
    30    70
   / \    / \
  20 40  60 80

Inorder Output: 20, 30, 40, 50, 60, 70, 80

5. Preorder and Postorder Traversals

Preorder (Root-Left-Right): Useful to create a copy of the tree.
Postorder (Left-Right-Root): Useful to delete the tree.

Balanced vs Unbalanced BST

A balanced BST ensures minimum possible height, improving efficiency. An unbalanced BST becomes skewed and loses performance benefits.

Balanced BST: Height ~ log(n)

Skewed BST Example: Inserting sorted values:

This turns BST into a linked list with O(n) complexity for operations.

Applications of BST

Symbol Table management in compilers
Indexing and Database Management Systems
In-memory sorting (via inorder traversal)
Routing algorithms
Hierarchical storage systems

Limitations of BST

Performance degrades if tree becomes unbalanced
Rebalancing requires complex operations (solved by AVL or Red-Black Trees)

Advanced BST Variants

AVL Tree: Self-balancing BST maintaining height balance.
Red-Black Tree: Balanced BST used in Java and C++ libraries.
Splay Tree: Recently accessed elements moved to the root.

Time and Space Complexities

Operation	Average Case	Worst Case
Search	O(log n)	O(n)
Insertion	O(log n)	O(n)
Deletion	O(log n)	O(n)
Space	O(n)	O(n)

🔹 Short Answer Questions (2-3 Marks)

What is a binary search tree? A BST is a binary tree where each node follows the property: left child < parent < right child.
What is inorder traversal of BST? Inorder traversal visits nodes in left-root-right order and returns nodes in sorted order.
What is the time complexity of insertion in BST? Average case: O(log n), worst case: O(n) for skewed trees.
How is a node with two children deleted in BST? Replace the node’s value with its inorder successor or predecessor, then delete that node.
What happens when a BST becomes unbalanced? The time complexity of operations may degrade to O(n), reducing efficiency.
Mention two applications of BST. Symbol tables in compilers and index management in databases.
Define preorder traversal. Preorder visits nodes in the order: root, left subtree, right subtree.

🔸 Long Answer Questions (5-10 Marks)

Explain the process of insertion and deletion in BST with suitable examples and diagrams. Insertion starts from the root and places the node based on value comparisons. Deletion involves handling three cases—leaf node, single child, or two children. In two-child deletion, we replace the node with its inorder successor and remove the successor node.
Compare BST with AVL tree. Which one is better and why? BST is simple and faster to implement but can become unbalanced. AVL tree maintains balance using rotations, ensuring O(log n) complexity even in the worst case. AVL is better for dynamic datasets requiring frequent insertions and deletions.
Describe the significance of inorder traversal in BST with an example. Inorder traversal visits nodes in sorted order. Example: BST with values 50, 30, 70, 20, 40, 60, 80 will produce output 20, 30, 40, 50, 60, 70, 80 using inorder traversal.
Write an algorithm for searching a node in BST and explain its complexity. Start from root. If key = node’s key, return success. If key < node, move left; else move right. Repeat until null or found. Time complexity is O(h) where h is tree height.
What are the limitations of BST? How can they be overcome? BSTs become inefficient if unbalanced. This can be overcome by using self-balancing trees like AVL or Red-Black Trees.

📝 Chapter Summary

BST is a binary tree where left subtree has smaller keys and right subtree has larger keys BST supports efficient insertion, deletion, and searching in O(log n) time in average cases Basic operations include insertion, searching, deletion, and tree traversals BSTs can become unbalanced, leading to poor performance Balanced BSTs like AVL and Red-Black Trees help maintain O(log n) operations Inorder traversal gives sorted output Applications include symbol tables, database indexing, and memory organization

📘 Model Paper / Sample Internal Exam Questions

Write an algorithm to insert a node in a BST and explain with an example.
Differentiate between binary tree and binary search tree with examples.
How does deletion work in a BST for a node with two children?
Draw a BST for the following values and write its inorder traversal: 40, 20, 60, 10, 30, 50, 70
Explain any three advantages and two limitations of BST.