Insertion in BST in Data Structures Theory - Full Explanation

Introduction

Imagine you have a collection of numbers and you want to keep them organized so you can find any number quickly. The problem is how to add a new number into this collection without losing the order that helps you find numbers fast.

Explanation

Binary Search Tree Structure

A binary search tree (BST) is a special kind of tree where each node has at most two children. The left child contains values smaller than the node, and the right child contains values larger than the node. This structure helps keep data sorted and easy to search.

BST keeps data sorted by placing smaller values to the left and larger values to the right.

Finding the Correct Position

To insert a new value, start at the root and compare the new value with the current node. If the new value is smaller, move to the left child; if larger or equal, move to the right child. Repeat this until you find an empty spot where the new value fits.

Insertion finds the right spot by comparing values and moving left or right accordingly.

Inserting the New Node

Once the correct empty position is found, place the new value there as a new node. This keeps the BST property intact, meaning the tree remains sorted and balanced for efficient searching.

The new value is added as a leaf node where the search ends.

Handling Duplicate Values

Some BSTs do not allow duplicate values, while others may store duplicates in a specific way, such as always going to the right subtree. The insertion method must handle duplicates based on the chosen rule.

Duplicate handling depends on the BST rules and affects where duplicates are inserted.

Real World Analogy

Imagine a librarian placing new books on a shelf sorted by title. To add a new book, the librarian starts at the beginning and moves left or right depending on whether the new title comes before or after the current book, until finding the right empty spot to place it.

Binary Search Tree Structure → Books arranged on a shelf with titles in alphabetical order

Finding the Correct Position → Librarian comparing new book title with existing books to find the right spot

Inserting the New Node → Placing the new book in the empty space found on the shelf

Handling Duplicate Values → Deciding where to put a book if another book has the same title

Diagram

Diagram

       ┌─────┐
       │  10 │
       ├─────┤
       │     │
       └─┬─┬─┘
         │ │
     ┌───┘ └───┐
     │         │
   ┌─┴─┐     ┌─┴─┐
   │ 5 │     │ 15│
   └───┘     └───┘

Insert 12:
Start at 10 → 12 > 10, go right
At 15 → 12 < 15, go left (empty)
Place 12 here.

This diagram shows a BST with nodes 10, 5, and 15, and the insertion path for the value 12.

Key Facts

Binary Search Tree (BST) → A tree where each node's left child is smaller and right child is larger than the node.

Insertion → Adding a new value by finding the correct empty spot following BST rules.

Leaf Node → A node with no children where new values are inserted.

Duplicate Handling → The rule deciding where to place values equal to existing nodes.

Code Example

Data Structures Theory

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
            return
        current = self.root
        while True:
            if value < current.value:
                if current.left is None:
                    current.left = Node(value)
                    return
                current = current.left
            else:
                if current.right is None:
                    current.right = Node(value)
                    return
                current = current.right

    def inorder(self, node, result):
        if node:
            self.inorder(node.left, result)
            result.append(node.value)
            self.inorder(node.right, result)

bst = BST()
bst.insert(10)
bst.insert(5)
bst.insert(15)
bst.insert(12)
result = []
bst.inorder(bst.root, result)
print(result)

Common Confusions

Believing new values can be inserted anywhere in the tree.

Believing new values can be inserted anywhere in the tree. Insertion must follow BST rules by comparing values and moving left or right to keep the tree sorted.

Thinking duplicates are always allowed and placed randomly.

Thinking duplicates are always allowed and placed randomly. Duplicates are handled by specific rules, often placed consistently in one subtree or not allowed.

Summary

Insertion in a BST keeps the tree sorted by placing smaller values to the left and larger to the right.

The process finds the correct empty spot by comparing the new value with existing nodes from the root down.

Handling duplicates depends on specific rules and affects where equal values are inserted.

Practice

1. What happens when you insert a new value smaller than the current node in a Binary Search Tree (BST)?

easy

A. The new value replaces the current node.

B. The new value is inserted in the right subtree of the current node.

C. The new value is inserted in the left subtree of the current node.

D. The new value is ignored.

Solution

1. Step 1: Understand BST insertion rule for smaller values

   In a BST, if the new value is smaller than the current node, it must go to the left subtree.

2. Step 2: Apply the rule to the insertion process

   The new value is inserted into the left subtree, maintaining BST order.

3. Final Answer:

   The new value is inserted in the left subtree of the current node. -> Option C

4. Quick Check:

   Smaller value goes left [OK]

Hint: Smaller values always go to the left subtree [OK]

Common Mistakes:

• Inserting smaller values to the right subtree
• Replacing the current node instead of inserting
• Ignoring the new value

2. Which of the following is the correct way to insert a value into an empty Binary Search Tree (BST)?

easy

A. Set the new value as the root node of the BST.

B. Insert the new value as the left child of a random node.

C. Ignore the new value since the tree is empty.

D. Insert the new value as the right child of a random node.

Solution

1. Step 1: Identify insertion behavior for an empty BST

   When the BST is empty, the first inserted value becomes the root node.

2. Step 2: Confirm the correct insertion method

   Setting the new value as the root node initializes the BST correctly.

3. Final Answer:

   Set the new value as the root node of the BST. -> Option A

4. Quick Check:

   Empty tree insertion sets root [OK]

Hint: First insertion always becomes the root node [OK]

Common Mistakes:

• Trying to insert as child without a root
• Ignoring insertion in empty tree
• Inserting randomly without root

3. Consider the BST below:

    10
   /  
  5   15

What will the BST look like after inserting the value 12?

medium

A. 10
/
5 15
/
12

B. 10
/
5 12

15

C. 10
/
5 15

12

D. 10
/
5 12
/
15

Solution

1. Step 1: Compare 12 with root and right child

   12 is greater than 10, so move to right subtree. 12 is less than 15, so it goes to the left of 15.

2. Step 2: Insert 12 as left child of 15

   Place 12 as the left child of node 15 to maintain BST order.

3. Final Answer:

   12 is inserted as left child of 15. -> Option A

4. Quick Check:

   12 > 10 and 12 < 15, so left of 15 [OK]

Hint: Compare stepwise: left if smaller, right if larger [OK]

Common Mistakes:

• Inserting 12 as right child of 15
• Inserting 12 as right child of 10
• Ignoring BST order rules

4. Identify the error in the following BST insertion pseudocode:

function insert(node, value):
  if node is null:
    return new Node(value)
  if value > node.value:
    node.left = insert(node.left, value)
  else:
    node.right = insert(node.right, value)
  return node

medium

A. The code inserts smaller values to the left subtree instead of right.

B. The code does not handle the base case for empty tree.

C. The code incorrectly returns null instead of the node.

D. The code inserts larger values to the left subtree instead of right.

Solution

1. Step 1: Analyze insertion direction for larger values

   The code inserts values greater than current node into the left subtree, which is incorrect.

2. Step 2: Correct insertion direction for BST

   Larger values should be inserted into the right subtree to maintain BST order.

3. Final Answer:

   The code inserts larger values to the left subtree instead of right. -> Option D

4. Quick Check:

   Larger values go right, not left [OK]

Hint: Larger values always go right subtree [OK]

Common Mistakes:

• Swapping left and right insertion conditions
• Missing base case for null node
• Returning wrong node after insertion

5. You have a BST with values 20, 10, 30, 25, and 40 inserted in that order. Now you want to insert 30 again. Where should the new 30 be inserted according to standard BST insertion rules?

hard

A. As the left child of the existing 30 node.

B. As the right child of the existing 30 node.

C. Replace the existing 30 node with the new 30.

D. Do not insert duplicates in BST.

Solution

1. Step 1: Understand BST insertion for equal values

   Standard BST insertion places values equal to the current node in the right subtree.

2. Step 2: Insert new 30 as right child of existing 30

   The new 30 should be inserted as the right child of the existing 30 node.

3. Final Answer:

   As the right child of the existing 30 node. -> Option B

4. Quick Check:

   Equal values go right subtree [OK]

Hint: Equal values go to right subtree in BST [OK]

Common Mistakes:

• Inserting duplicates to the left subtree
• Replacing existing nodes instead of inserting
• Ignoring duplicates insertion rules