BST Insert Operation in DSA Typescript - 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. For every node, all values in the left subtree are smaller, and all values in the right subtree are larger than the node's value.

beginner

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

Compare the new value with the current node's value. If smaller, go to the left child; if larger, go to the right child. Repeat until you find an empty spot to insert the new node.

intermediate

Why do we insert nodes recursively or iteratively in a BST?

Because we need to follow the BST property at each step, checking left or right child until we find the correct empty spot to insert the new node.

intermediate

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

Usually, BSTs do not allow duplicate values. The insert operation can ignore the duplicate or handle it based on specific rules, like inserting duplicates to the right subtree.

intermediate

What is the time complexity of inserting a node in a BST?

The average time complexity is O(log n) when the tree is balanced, but in the worst case (like a skewed tree), it can be O(n), where n is the number of nodes.

When inserting a value into a BST, if the value is less than the current node, where do you go next?

A Replace current node

B Right child

C Left child

D Stop insertion

In a BST, smaller values go to the left child.

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

A Create a new root node with the value

B Search for the value

C Insert as left child

D Insert as right child

If the BST is empty, the new value becomes the root node.

What is the worst-case time complexity of inserting a node in a BST?

A O(log n)

B O(n)

C O(1)

D O(n log n)

In the worst case, the BST becomes skewed, making insertion O(n).

If a BST already contains the value you want to insert, what usually happens?

A Insert duplicate to the left

B Insert duplicate to the right

C Replace the existing node

D Ignore the duplicate

Most BST implementations ignore duplicates to keep unique values.

Which traversal method is NOT used to insert a node in a BST?

A In-order traversal

B Going left or right child based on comparison

C Following BST property by comparing values

D Pre-order traversal

In-order traversal is for visiting nodes, not for insertion.

Explain step-by-step how to insert a new value into a Binary Search Tree.

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

Describe the time complexity of inserting a node in a BST and what affects it.

Consider how the shape of the tree changes the steps needed.

Practice

1. What is the main purpose of the insert operation in a Binary Search Tree (BST)?

easy

A. To add a new node while keeping the BST property intact

B. To delete a node from the BST

C. To find the maximum value in the BST

D. To balance the BST after insertion

Solution

1. Step 1: Understand BST property

   A BST keeps nodes ordered so that left child is smaller and right child is larger than the parent.

2. Step 2: Purpose of insert operation

   Insert adds a new node in the correct position to maintain this order.

3. Final Answer:

   To add a new node while keeping the BST property intact -> Option A

4. Quick Check:

   Insert = Add node maintaining order [OK]

Hint: Insert adds nodes without breaking BST order [OK]

Common Mistakes:

• Confusing insert with delete operation
• Thinking insert balances the tree automatically
• Assuming insert finds max or min values

2. Which of the following is the correct TypeScript function signature for inserting a value into a BST node?

easy

A. function insert(root: Node, value: number): void

B. function insert(value: number, root: Node): void

C. function insert(root: Node | null, value: number): Node | null

D. function insert(root: Node, value: string): Node

Solution

1. Step 1: Analyze parameter types

   Insert needs the root node (which can be null if tree is empty) and the value to insert (a number).

2. Step 2: Analyze return type

   It returns the updated root node (Node or null if empty).

3. Final Answer:

   function insert(root: Node | null, value: number): Node | null -> Option C

4. Quick Check:

   Correct params and return type [OK]

Hint: Insert returns updated root, accepts root or null [OK]

Common Mistakes:

• Swapping parameter order
• Using void return type instead of returning Node
• Using wrong value type like string

3. Given the following BST and the insert operation call insert(root, 7), what will be the in-order traversal of the BST after insertion?

Initial BST in-order: 3 -> 5 -> 8 -> 10

Code snippet:

class Node {
  constructor(public val: number, public left: Node | null = null, public right: Node | null = null) {}
}

function insert(root: Node | null, val: number): Node {
  if (!root) return new Node(val);
  if (val < root.val) root.left = insert(root.left, val);
  else root.right = insert(root.right, val);
  return root;
}

medium

A. [3, 5, 8, 7, 10]

B. [3, 5, 8, 10, 7]

C. [7, 3, 5, 8, 10]

D. [3, 5, 7, 8, 10]

Solution

1. Step 1: Locate insertion point for 7

   7 is greater than 5 but less than 8, so it goes to the left of 8.

2. Step 2: Perform in-order traversal after insertion

   In-order visits left, root, right: 3, 5, 7, 8, 10.

3. Final Answer:

   [3, 5, 7, 8, 10] -> Option D

4. Quick Check:

   In-order sorted after insert [OK]

Hint: Insert left if smaller, right if larger [OK]

Common Mistakes:

• Placing 7 incorrectly after 8
• Confusing in-order traversal order
• Ignoring recursive insert logic

4. The following TypeScript code attempts to insert a value into a BST but has a bug. What is the error?

function insert(root: Node | null, val: number): Node {
  if (root === null) {
    return new Node(val);
  }
  if (val <= root.val) {
    insert(root.left, val);
  } else {
    insert(root.right, val);
  }
  return root;
}

medium

A. The base case is missing

B. The recursive calls do not update root.left or root.right

C. The function returns void instead of Node

D. The comparison operator should be < instead of <=

Solution

1. Step 1: Check recursive calls

   The calls to insert do not assign the result back to root.left or root.right, so tree structure is not updated.

2. Step 2: Correct recursive assignment

   Should be root.left = insert(root.left, val) or root.right = insert(root.right, val) to update links.

3. Final Answer:

   The recursive calls do not update root.left or root.right -> Option B

4. Quick Check:

   Must assign recursive insert result to child [OK]

Hint: Always assign recursive insert result to child node [OK]

Common Mistakes:

• Forgetting to assign recursive call result
• Misunderstanding base case presence
• Changing comparison operator unnecessarily

5. You have a BST with nodes 10, 5, 15, 3, 7, 12, 18. You want to insert 6. Which sequence of nodes will you visit during the insert operation?

hard

A. [10, 5, 7]

B. [10, 15, 12]

C. [10, 5, 3]

D. [10, 15, 18]

Solution

1. Step 1: Start at root 10

   6 is less than 10, so move to left child 5.

2. Step 2: Compare with 5 and 7

   6 is greater than 5, move to right child 7. 6 is less than 7, so insert here.

3. Final Answer:

   [10, 5, 7] -> Option A

4. Quick Check:

   Traverse nodes comparing 6 until insertion point [OK]

Hint: Follow left/right based on comparison until null [OK]

Common Mistakes:

• Visiting wrong subtree based on comparison
• Skipping nodes in path
• Confusing insertion path with traversal order