Algorithm Room Login Get Started

Binary Search Tree

In the world of data structures, binary search trees (BSTs) play a crucial role in organizing and managing data efficiently. A BST is a special type of binary tree that maintains a specific ordering property all elements in the left sub-tree of a node are smaller than the node itself, while all elements in the right sub-tree are larger.

This structure allows for fast searching, insertion, and deletion operations, making BSTs highly valuable for solving a wide range of computational problems.

From database indexing to expression parsing and memory management, BSTs form the backbone of many real-world systems.

A Binary Search Tree (BST) is a special type of binary tree where:

  • The left sub-tree of a node contains only nodes with values less than the node’s value.
  • The right sub-tree contains only nodes with values greater than the node’s value.
  • No duplicate nodes are allowed.
  • Each sub-tree must also be a binary search tree.

Properties of a Binary Search Tree

  1. The root node divides all values into two groups:
    • Left Sub-tree: all smaller values
    • Right Sub-tree: all larger values
  2. The inorder traversal of a BST always gives sorted values.
  3. Efficient for searching, insertion, and deletion (average case: O(log n)).

Operations on Binary Search Tree (BST)

A Binary Search Tree allows several fundamental operations that make it efficient for storing, searching, and modifying sorted data.

1. Insertion

To insert a new value into the tree while maintaining the BST property.

  • If the tree is empty, the new value becomes the root.
  • If the value is less than the current node, insert it into the left sub-tree.
  • If the value is greater than the current node, insert it into the right sub-tree.

Example: Insert 40 into this BST

     50
    /  \
  30    70
  • 40 < 50 → go left
  • 40 > 30 → go right → insert as right child of 30

Resulting tree

	 50
    /  \
  30    70
    \
    40

2. Search

To check whether a specific value exists in the tree.

  • Compare the target value with the current node.
  • If equal → value found.
  • If smaller → search left.
  • If larger → search right.
  • If null → value does not exist in the tree.

Example: Search for 70

     50
    /  \
  30    70
  • 70 > 50 → go right → found.

3. Deletion

To remove a node from the tree and maintain the BST structure.

  • Node has no children (leaf node): Simply delete it.
  • Node has one child: Replace the node with its child.
  • Node has two children:
    • Find the inorder successor (smallest in right sub-tree) or inorder predecessor (largest in left sub-tree).
    • Replace the node’s value with that.
    • Delete the successor/predecessor.

Example: Delete 50

   50
  /  \
30    70
     /  \
    60  80
   /
 55
  • 50 has two children.
  • Find the Inorder Successor of 50 (Inorder successor = smallest node in the right subtree of 50)
  • Right sub-tree of 50 is
        70
      /   \
 	60     80
   /
 55
  • Start from 70, move left until you reach the smallest node.
    • 70 → left → 60
    • 60 → left → 55
    • 55 has no left child → stop.
  • Inorder successor of 50 is 55
  • Replace 50 with 55
  • Delete original 55

Result Tree

    55
   /  \
 30    70
      /  \
    60    80

4. Traversal

To visit all nodes of the tree in a specific order.

a. Inorder Traversal (Left, Root, Right)

Returns the elements in sorted order.

Example: For this tree

     50
    /  \
  30    70

Inorder: 30, 50, 70

b. Preorder Traversal (Root, Left, Right)

Useful for saving or cloning a tree.

Preorder: 50, 30, 70

c. Postorder Traversal (Left, Right, Root)

Used in deleting/freeing the tree.

Postorder: 30, 70, 50

d. Level-order Traversal

Visits nodes level by level (uses a queue).

Level-order: 50, 30, 70

5. Finding Minimum and Maximum

Minimum: Keep going to the leftmost node.

Maximum: Keep going to the rightmost node.

Example:

     50
    /  \
  30    70
 /         \
20         90

Minimum: 20

Maximum: 90

6. Find Height

To determine the maximum depth of the tree.

  • Height of a node is 1 + max(left subtree height, right subtree height)
  • Height of empty tree = -1 or 0

7. Check Validity of BST

Ensure that a given binary tree satisfies the BST rules.

  • Use a recursive function that checks:
  • Left sub-tree values < current node
  • Right sub-tree values > current node
  • Do this recursively for all nodes

8. Lowest Common Ancestor (LCA)

To find the lowest node that is an ancestor of two given nodes in the BST.

  • If both values < current → go left
  • If both values > current → go right
  • Else → current node is LCA

Rules for Creating Binary Search Tree

Each node has at most two children

  • A BST is a binary tree, so every node can have zero, one, or two children.

The left child contains a smaller value

  • The value in the left child (and all nodes in the left sub-tree) must be less than the value in the parent node.

The right child contains a greater value

  • The value in the right child (and all nodes in the right sub-tree) must be greater than the value in the parent node.

No duplicate values

  • Standard BSTs do not allow duplicate values. Each node must contain a unique key.

Recursive rule applies to all sub-tree

  • Every left and right subtree must also be a BST. This recursive structure is essential to maintain the BST property.

Order of insertion affects the structure

  • The shape of the BST depends on the order in which elements are inserted. A different insertion order can result in a different tree, even if the elements are the same.

Example

Insert values in this order: 50, 30, 70, 20, 40, 60, 80

  • 50 → root
  • 30 < 50 → left of 50
  • 70 > 50 → right of 50
  • 20 < 30 → left of 30
  • 40 > 30 → right of 30
  • 60 < 70 → left of 70
  • 80 > 70 → right of 70

Final Tree Structure

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

This tree follows all BST creation rules.

Time and Space Complexity of BST Operations

Time Complexity

OperationBest / Average Case TimeWorst Case Time
SearchO(log n)O(n)
InsertionO(log n)O(n)
DeletionO(log n)O(n)
TraversalO(n)O(n)
Find Min/MaxO(log n)O(n)
HeightO(n)O(n)
  • n = number of nodes in the BST
  • Best/Average Case happens when the tree is balanced, i.e., the height is log n.
  • Worst Case occurs when the BST becomes a linked list (skewed), i.e., height becomes n.

Space Complexity

Space Complexity includes recursive call stack (for traversal or operations).

OperationSpace Complexity
SearchO(n) (recursive stack)
InsertionO(n) (recursive stack)
DeletionO(n) (recursive stack)
TraversalO(n)
Find Min/MaxO(1)
HeightO(n)

Numerical Questions on Binary Search Tree Creation

  1. Create a BST by inserting the following elements in the given order 50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24
    • Draw the resulting BST.
    • Perform inorder, preorder, and postorder traversals.
    • Find the minimum and maximum element in the tree.
  2. Insert the following values into a BST: 25, 15, 10, 22, 35, 30, 70, 90, 45
    • Draw the BST.
    • What is the height of the BST?
    • Delete the node with value 35 and draw the updated BST.
  3. Given the values: 50, 70, 60, 20, 90, 10, 40, 100
    • Construct the BST.
    • Find the inorder successor of node 60.
    • Find the lowest common ancestor (LCA) of 62 and 75.
  4. Create a BST using the following sequence: 100, 80, 120, 70, 90, 110, 130. Perform all four traversals.
    • Inorder
    • Preorder
    • Postorder
    • Level-order
    • Search for the value 95 in the BST and show the steps.
  5. Given this BST (constructed by inserting in order): 40, 20, 60, 10, 30, 50, 70
    • Delete the root node 40.
    • Redraw the tree after deletion.
    • Is the resulting tree still a valid BST?
  6. Insert the following numbers: 55, 20, 80, 10, 30, 25, 90, 85, 15
    • Draw the resulting BST.
    • Find the depth of node 25.
    • Check whether node 90 is a leaf node.
Previous
Introduction to Algorithm
Next
Recursion Algorithm
Contents