BST Search 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 nodes in its left subtree have smaller values, and all nodes in its right subtree have larger values.

beginner

How does the search operation work in a BST?

Start at the root. If the value equals the node's value, return it. If smaller, search the left subtree. If larger, search the right subtree. Repeat until found or reach a null node.

intermediate

What is the time complexity of searching in a BST?

The average time complexity is O(log n) when the tree is balanced. In the worst case (skewed tree), it can be O(n).

beginner

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

The search will continue down the tree until it reaches a null node, meaning the value is not present. The operation returns null or indicates not found.

intermediate

Show the TypeScript code snippet for searching a value in a BST node.

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

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

A Root node

B Right subtree

C Sibling node

D Left subtree

In a BST, smaller values are always in the left subtree.

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

A O(n)

B O(1)

C O(log n)

D O(n log n)

Balanced BST search takes O(log n) time because the tree height is log n.

If the search value equals the current node's value, what should the search operation do?

A Return the current node

B Search left subtree

C Search right subtree

D Return null

When the value matches, the search returns the current node immediately.

What does the search operation return if the value is not found in the BST?

A The root node

B Null or not found

C The smallest node

D The last visited node

If the value is not found, the search returns null or indicates not found.

Which traversal method is used in the BST search operation?

A Directed search based on value comparison

B Preorder traversal

C Postorder traversal

D Inorder traversal

BST search uses directed search by comparing values, not a full traversal.

Explain how the search operation works in a Binary Search Tree.

Think about how you decide which way to go at each node.

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

Consider how the shape of the tree changes search speed.

Practice

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

easy

A. To delete a value from the BST

B. To insert a new value into the BST

C. To find whether a given value exists in the BST

D. To traverse all nodes in the BST

Solution

1. Step 1: Understand the purpose of search in BST

   The search operation is designed to check if a specific value is present in the BST.

2. Step 2: Differentiate from other operations

   Insertion adds new values, deletion removes values, and traversal visits all nodes. Search only checks existence.

3. Final Answer:

   To find whether a given value exists in the BST -> Option C

4. Quick Check:

   Search = Find value presence [OK]

Hint: Search checks presence, not insertion or deletion [OK]

Common Mistakes:

• Confusing search with insert or delete
• Thinking search returns all nodes
• Assuming search modifies the tree

2. Which of the following is the correct TypeScript function signature for a BST search method that returns a boolean?

easy

A. function search(root: TreeNode | null, value: number): boolean

B. function search(value: number): TreeNode

C. function search(root: TreeNode, value: string): boolean

D. function search(root: TreeNode | null, value: number): void

Solution

1. Step 1: Analyze parameter types

   The search needs the root node (which can be null) and the value to find (a number).

2. Step 2: Analyze return type

   Search returns true or false, so return type should be boolean.

3. Final Answer:

   function search(root: TreeNode | null, value: number): boolean -> Option A

4. Quick Check:

   Correct params and boolean return [OK]

Hint: Search returns boolean, root can be null [OK]

Common Mistakes:

• Using wrong parameter types
• Returning void instead of boolean
• Using string instead of number for value

3. Given the BST below and the search function call search(root, 7), what will be the output?

BST structure:
10
/ \
5 15
/ \ \
3 7 20

Code snippet:

function search(root: TreeNode | null, value: number): boolean {
  if (!root) return false;
  if (root.val === value) return true;
  if (value < root.val) return search(root.left, value);
  return search(root.right, value);
}

console.log(search(root, 7));

medium

A. false

B. Error

C. undefined

D. true

Solution

1. Step 1: Trace search for value 7

   Start at root 10: 7 < 10, go left to 5. Then 7 > 5, go right to 7.

2. Step 2: Check node value

   Node value is 7, matches search value, so return true.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Found 7 in BST = true [OK]

Hint: Follow BST rules left/right to find value [OK]

Common Mistakes:

• Stopping search too early
• Confusing left and right child directions
• Returning false when node matches

4. The following TypeScript search function for a BST has a bug. What is the error?

function search(root: TreeNode | null, value: number): boolean {
  if (root === null) return false;
  if (root.val === value) return true;
  if (value > root.val) return search(root.left, value);
  else return search(root.right, value);
}

medium

A. The comparison operator should be >= instead of >

B. The recursive calls to left and right children are swapped

C. The function does not return a boolean

D. The base case is missing

Solution

1. Step 1: Check recursive calls logic

   For BST, if value > root.val, search should go right, but code goes left.

2. Step 2: Confirm swapped children calls

   Similarly, else goes right instead of left. So left and right calls are swapped.

3. Final Answer:

   The recursive calls to left and right children are swapped -> Option B

4. Quick Check:

   Left/right calls swapped = bug [OK]

Hint: Value > root goes right, not left [OK]

Common Mistakes:

• Mixing left and right child in recursion
• Ignoring base case (though present here)
• Wrong comparison operators

5. You want to search for a value in a BST that may contain duplicate values on the right subtree. Which modification to the standard BST search logic ensures you find the first occurrence of the value?

Choose the correct approach:

hard

A. Always search left subtree when value equals current node's value

B. Return true immediately when value equals current node's value

C. Search right subtree when value equals current node's value to find duplicates

D. Traverse entire tree inorder to find all occurrences

Solution

1. Step 1: Understand duplicate placement in BST

   Duplicates are stored in right subtree, so first occurrence is the leftmost matching node.

2. Step 2: Modify search to find first occurrence

   When value equals current node, continue searching left subtree to find earlier occurrence.

3. Final Answer:

   Always search left subtree when value equals current node's value -> Option A

4. Quick Check:

   Search left on equal to find first duplicate [OK]

Hint: On equal, go left to find first duplicate [OK]

Common Mistakes:

• Stopping search immediately on equal
• Searching right subtree on equal
• Doing full inorder traversal unnecessarily