Insertion in BST in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Binary Search Tree (BST)?

A Binary Search Tree is a tree data structure where each node has at most two children. The left child's value is less than the parent's value, and the right child's value is greater than the parent's value. This property helps in efficient searching, insertion, and deletion.

beginner

What is the main rule to follow when inserting a new value into a BST?

When inserting, compare the new value with the current node's value. If it is smaller, go to the left child; if larger, go to the right child. Repeat this until you find an empty spot where the new value can be inserted as a leaf node.

beginner

Why do we insert new nodes as leaf nodes in a BST?

New nodes are inserted as leaf nodes because the BST property requires that all nodes to the left are smaller and all to the right are larger. Inserting at a leaf maintains this order without disturbing the existing structure.

intermediate

What happens if you try to insert a value that already exists in the BST?

Typically, BSTs do not allow duplicate values. If a duplicate is found during insertion, the process stops or handles it based on specific rules, such as ignoring the insertion or storing duplicates in a special way.

intermediate

How does the insertion operation affect the height of a BST?

Insertion can increase the height of the BST by one if the new node is added at the deepest level. Over many insertions, if values are inserted in sorted order, the BST can become unbalanced and behave like a linked list, increasing height and reducing efficiency.

Where do you insert a new value in a BST if it is smaller than the current node's value?

A Anywhere in the tree

B In the right subtree

C At the root

D In the left subtree

In a BST, smaller values go to the left subtree to maintain the order property.

What is the first step when inserting a new value into a BST?

A Compare the new value with the root node

B Insert the value at the leftmost leaf

C Delete the root node

D Balance the tree

Insertion starts by comparing the new value with the root to decide the path.

What happens if you insert values in sorted order into a BST?

A The BST becomes balanced

B The BST becomes a linked list

C The BST height decreases

D The BST deletes nodes

Inserting sorted values creates a skewed tree like a linked list, increasing height.

Can a BST contain duplicate values?

A Yes, duplicates are always allowed

B No, duplicates are never allowed

C Usually no, but some BSTs handle duplicates specially

D Duplicates replace existing nodes

Most BSTs do not allow duplicates, but some implementations handle them with special rules.

Where is a new node inserted in a BST?

A As a leaf node

B At the root

C In the middle of the tree

D At the rightmost node always

New nodes are inserted as leaf nodes to maintain BST properties.

Explain the step-by-step process of inserting a new value into a Binary Search Tree.

Think about how you decide where to place the new value by comparing it with existing nodes.

Describe how inserting values in sorted order affects the shape and efficiency of a BST.

Consider what happens when every new value is always greater than the previous.

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