BST Insert Operation in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Binary Search Tree (BST)?

A BST is a tree where each node has at most two children. The left child's value is less than the parent node's value, and the right child's value is greater. This helps in fast searching and insertion.

beginner

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

Compare the new value with the current node. 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 in a BST?

Recursion helps to move down the tree easily by calling the same insert function on left or right child until the correct empty spot is found.

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 will find the existing value and not insert a new node.

beginner

Show the state of BST after inserting 5, 3, 7 in an empty BST.

5 is the root node, with 3 as its left child and 7 as its right child. Both 3 and 7 have null children.

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

A Go to the right child

B Go to the left child

C Replace the current node

D Stop insertion

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

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

A O(log n)

B O(1)

C O(n)

D O(n log n)

In a balanced BST, insertion takes O(log n) time because we halve the search space at each step.

If the BST is empty, what happens when you insert a new value?

A The tree remains empty

B Insertion fails

C The new value becomes a leaf node

D The new value becomes the root node

If the BST is empty, the first inserted value becomes the root.

Which traversal order is best to print BST values in ascending order?

A Inorder

B Preorder

C Postorder

D Level order

Inorder traversal visits nodes in ascending order in a BST.

What is the first step in the BST insert operation?

A Create a new node

B Traverse to the right child

C Compare the value with the root node

D Delete the root node

Insertion starts by comparing the new value with the root node.

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

Think about how you decide where to place the new value.

Describe what the BST looks like after inserting the values 10, 5, 15, 3, 7 in order.

Draw the tree step by step as you insert each value.