NoteVerse

Binary Search Tree - Operations

Comprehensive study notes, diagrams, and exam preparation for Binary Search Tree - Operations.

Binary Search Tree - Operations

Definition

A Binary Search Tree (BST) is a binary tree in which, for every node:

  • all keys in the left subtree are less than the node’s key
  • all keys in the right subtree are greater than the node’s key
  • both left and right subtrees are also BSTs

This ordering property allows efficient operations such as search, insertion, deletion, minimum/maximum finding, and inorder traversal.

Example:

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

In this tree, every node satisfies the BST property. For example, 30 is less than 50, so it appears in the left subtree, while 70 is greater than 50, so it appears in the right subtree.

Main Content

1. Search Operation

Purpose and logic

The search operation in a BST is used to find whether a given key exists in the tree. The process begins at the root and compares the target value with the current node’s key. If the target is smaller, the search moves to the left subtree; if larger, it moves to the right subtree. This continues until the item is found or the search reaches a null pointer, which means the key is not present.

Example and time complexity

Suppose we search for 60 in the BST below:

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

Search path:

  • 60 > 50 → go right
  • 60 < 70 → go left
  • 60 = 60 → found

The efficiency of search depends on the height of the tree.

  • Best case: O(1) if the key is at the root
  • Average case: O(log n) for a balanced BST
  • Worst case: O(n) for a skewed tree

2. Insertion Operation

Purpose and process

Insertion adds a new key into the BST while preserving the BST property. The new value is compared with nodes starting from the root, and its position is determined by moving left for smaller values and right for larger values until an empty spot is found.

Example

Insert 65 into the tree:

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

Steps:

  • 65 > 50 → move right
  • 65 < 70 → move left
  • 65 > 60 → move right
  • Insert 65 as the right child of 60

Resulting tree:

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

Important note

Insertion is efficient when the tree remains balanced. In an unbalanced tree, insertion can take O(n) time because the path may become as long as the number of nodes.

3. Deletion Operation

Purpose and cases

Deletion is the most complex BST operation because removing a node must still preserve the BST property. There are three main cases:

  • Case 1: Node is a leaf
    If the node has no children, simply remove it.

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

  • Case 3: Node has two children
    Replace the node with either:

    • its inorder successor (smallest node in the right subtree), or
    • its inorder predecessor (largest node in the left subtree)

    Then delete that replacement node from its original position.

Example

Delete 50 from:

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

Since 50 has two children:

  • find inorder successor = 60
  • replace 50 with 60
  • remove 60 from its original location

Final tree:

          60
         /  \
       30    70
      / \      \
     20 40     80

Why it is important

Deletion maintains ordered structure but requires careful restructuring. It is often used in dynamic datasets where items are frequently added and removed.

Working / Process

1. Start from the root and compare keys

Every BST operation begins at the root node. For searching, insertion, and deletion, the target key is compared with the current node. If the target is smaller, go left; if larger, go right. This repeated comparison is what gives BSTs their efficiency.

2. Follow the BST ordering property until the required node or position is found

The tree is traversed along only one path at a time, instead of checking all nodes. This path leads either to the target node, the insertion point, or the node to be deleted. For deletion, the structural case must first be identified: leaf, one child, or two children.

3. Apply the required change and preserve the BST structure

  • For search, report whether the key is found.
  • For insertion, attach the new node at the correct null position.
  • For deletion, reconnect subtrees properly using child replacement or inorder successor/predecessor.
    After the update, the BST property must remain valid for every node.

Advantages / Applications

Efficient ordered data handling

BSTs store data in sorted order, making it easy to find minimum, maximum, predecessor, successor, and sorted traversal using inorder traversal.

Fast average-time operations

Search, insertion, and deletion are all efficient in a balanced BST, typically operating in O(log n) time, which is much better than linear searching in arrays or linked lists.

Widely used in real-world systems

BSTs are used in:

  • database indexing
  • symbol tables in compilers
  • dictionary and set implementations
  • maintaining dynamic ordered collections
  • range query processing and hierarchical data storage

Summary

A Binary Search Tree organizes data in sorted order so that searching, insertion, and deletion can be done efficiently. Its main strength lies in using the left-right ordering rule to reduce unnecessary comparisons and keep operations fast when the tree remains balanced.

  • BST follows an ordered left-subtree and right-subtree rule
  • Search, insertion, and deletion are the main BST operations
  • Balanced trees give much better performance than skewed trees
  • Important terms to remember: root, left subtree, right subtree, inorder successor, inorder predecessor, leaf node, balanced tree
← Prev: degree
Next: Traversal →