BST Search Operation in DSA C++ - 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's value, and the right child's value is greater. This helps in fast searching.

beginner

How does the search operation work in a BST?

Start at the root. If the value equals the node's value, stop. If smaller, go left. If larger, go right. Repeat until found or no more nodes.

beginner

Why is BST search faster than searching in a list?

BST search skips half of the tree at each step by choosing left or right child based on comparison, unlike a list which checks each item one by one.

intermediate

What is the time complexity of searching in a balanced BST?

The time complexity is O(log n) because each step halves the search space in a balanced BST.

beginner

What happens if the value is not found in the BST during search?

The search reaches a null child (no node), meaning the value is not in the tree.

In a BST, if the search value is less than the current node's value, where do you go next?

A Root node

B Right child

C Parent node

D Left child

If the search value is less, you move to the left child because all left children have smaller values.

What is the best case time complexity of searching in a BST?

A O(n)

B O(log n)

C O(1)

D O(n log n)

Best case is O(1) when the root node itself contains the search value.

If a BST is not balanced, what can happen to the search time?

A It becomes O(n)

B It becomes O(1)

C It stays O(log n)

D It becomes O(n log n)

If the BST is skewed (like a linked list), search time can degrade to O(n).

What is the first step in searching a value in a BST?

A Check the left child

B Compare with the root node

C Check the right child

D Insert the value

Search always starts by comparing the value with the root node.

If the search value is greater than the current node's value, where do you move next?

A Right child

B Left child

C Parent node

D Root node

You move to the right child because all right children have greater values.

Explain the step-by-step process of searching a value in a BST.

Think about how you decide which child to visit next.

Describe why BST search is more efficient than searching in an unsorted list.

Focus on how BST structure helps reduce search steps.