BST Insert Operation in DSA Javascript - 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 node's value, and the right child's value is greater than the parent 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 it is 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 use recursion or loops in BST insert operation?

Because we need to travel down the tree from the root to the correct leaf position where the new value fits, following the BST property. Recursion or loops help us move step-by-step through the nodes.

intermediate

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

Usually, BSTs do not allow duplicate values. The insert operation can ignore the new value or handle duplicates by a specific rule, like inserting to the right subtree.

beginner

Show the result of inserting 7 into this BST: 5 -> 3 -> 8 -> null

After inserting 7, the BST looks like: 5 -> 3 -> 8 -> 7 -> null. The 7 is inserted as the left child of 8 because 7 < 8.

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

A Left subtree

B Right subtree

C At the current node

D At the root

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

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

A O(log n)

B O(n)

C O(n log n)

D O(1)

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

If the BST is empty, where do you insert the new value?

A Cannot insert

B As the left child

C As the root node

D As the right child

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

What happens if you insert a value equal to a node's value in a typical BST?

A It causes an error

B It replaces the existing node

C It is inserted as left child

D It is ignored or handled by a rule

BSTs usually do not allow duplicates or handle them by a specific rule.

Which traversal method helps to verify the BST property after insertion?

A Post-order traversal

B In-order traversal

C Pre-order traversal

D Level-order traversal

In-order traversal of a BST prints values in sorted order, helping verify the BST property.

Explain step-by-step how to insert a new value into a BST.

Think about walking down the tree comparing values.

Describe what changes in the BST structure after inserting a new value.

Focus on where the new node fits and how the tree keeps order.