BST Insert Operation in DSA C++ - 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 nodes in its left subtree have smaller values, and all nodes in its right subtree have larger values.

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

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 ignore the new value or handle duplicates based on specific rules, but commonly it does not insert duplicates.

beginner

Show the step-by-step insertion of 5 into this BST: 10 -> 4 -> 15

Start at root 10: 5 < 10, go left to 4. 5 > 4, go right which is empty. Insert 5 as right child of 4.

intermediate

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

The average time complexity is O(log n) if the tree is balanced, but in the worst case (like a linked list), it can be O(n).

When inserting a new value into a BST, where do you go if the new value is greater than the current node's value?

A To the left child

B To the right child

C Replace the current node

D Stop insertion

In a BST, values greater than the current node go to the right child.

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

A Compare with the root node

B Insert at the leftmost position

C Insert at the rightmost position

D Delete the root node

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

If a BST is unbalanced and looks like a linked list, what is the worst-case time complexity for insertion?

A O(n)

B O(log n)

C O(1)

D O(n log n)

In the worst case, insertion takes O(n) time if the BST is like a linked list.

Which of these is NOT true about BST insertion?

A Insertion compares values to decide direction

B Insertion follows the BST property

C Insertion finds the correct empty spot

D Duplicates are always inserted to the right

Duplicates are usually not inserted or handled specially; they are not always inserted to the right.

After inserting a new node, what property must the BST maintain?

A All left children are greater than the node

B All right children are smaller than the node

C Left subtree nodes are smaller, right subtree nodes are greater

D The tree becomes balanced automatically

BST property requires left subtree nodes to be smaller and right subtree nodes to be greater.

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

Think about walking down the tree comparing values.

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

Consider how deep the tree is.