BST Search Operation in DSA Typescript

Mental Model

A binary search tree lets you find a value by comparing and moving left or right, skipping half the tree each time.

Analogy: Like looking for a word in a dictionary by opening to the middle and deciding if you go to the front or back half based on the word's first letter.

      8
     / \
    3   10
   / \    \
  1   6    14
     / \   /
    4   7 13

Dry Run Walkthrough

Input: BST: 8 -> 3 -> 10 -> 1 -> 6 -> 14 -> 4 -> 7 -> 13, search value 7

Goal: Find if value 7 exists in the BST and show the path taken

Step 1: Start at root node 8

8 [curr] -> 3 -> 10 -> 1 -> 6 -> 14 -> 4 -> 7 -> 13

Why: We always start searching from the root

Step 2: 7 < 8, move curr to left child 3

8 -> 3 [curr] -> 10 -> 1 -> 6 -> 14 -> 4 -> 7 -> 13

Why: Since 7 is less than 8, search left subtree

Step 3: 7 > 3, move curr to right child 6

8 -> 3 -> 10 -> 1 -> 6 [curr] -> 14 -> 4 -> 7 -> 13

Why: 7 is greater than 3, so go right

Step 4: 7 > 6, move curr to right child 7

8 -> 3 -> 10 -> 1 -> 6 -> 14 -> 4 -> 7 [curr] -> 13

Why: 7 is greater than 6, continue right

Step 5: Found node with value 7, stop search

8 -> 3 -> 10 -> 1 -> 6 -> 14 -> 4 -> 7 [curr] -> 13

Why: Current node value matches search value

Result:

8 -> 3 -> 6 -> 7 -> null (found 7)

Annotated Code

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function searchBST(root: TreeNode | null, val: number): TreeNode | null {
  let curr = root;
  while (curr !== null) {
    if (val === curr.val) {
      return curr; // found the value
    } else if (val < curr.val) {
      curr = curr.left; // go left
    } else {
      curr = curr.right; // go right
    }
  }
  return null; // not found
}

// Build the example tree
const root = new TreeNode(8);
root.left = new TreeNode(3);
root.right = new TreeNode(10);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(6);
root.left.right.left = new TreeNode(4);
root.left.right.right = new TreeNode(7);
root.right.right = new TreeNode(14);
root.right.right.left = new TreeNode(13);

const searchVal = 7;
const foundNode = searchBST(root, searchVal);
if (foundNode) {
  console.log(`Found node with value: ${foundNode.val}`);
} else {
  console.log(`Value ${searchVal} not found in BST`);
}

while (curr !== null) {

keep searching while there are nodes to check

if (val === curr.val) {

check if current node has the value we want

return curr; // found the value

stop and return node when found

else if (val < curr.val) {

if value is smaller, go left

curr = curr.left; // go left

move current pointer to left child

else {

if value is bigger, go right

curr = curr.right; // go right

move current pointer to right child

Output

Found node with value: 7

Complexity Analysis

Time: O(h) where h is the height of the tree because we move down one level each step

Space: O(1) because we only use a pointer variable and no extra space

vs Alternative: Compared to searching a list which is O(n), BST search is faster if tree is balanced because it skips half the nodes each step

Edge Cases

Empty tree (root is null)

Returns null immediately, no nodes to search

DSA Typescript

while (curr !== null) {

Value not present in tree

Search goes down path until null, then returns null

DSA Typescript

while (curr !== null) {

Value is at root node

Returns root immediately without moving

DSA Typescript

if (val === curr.val) {

When to Use This Pattern

When you need to find a value quickly in a sorted tree structure, use BST search because it halves the search space each step.

Common Mistakes

Mistake: Not moving the current pointer correctly to left or right child
Fix: Use if-else to compare and assign curr = curr.left or curr.right accordingly

Mistake: Forgetting to check if current node is null before accessing its value
Fix: Use while loop condition curr !== null to avoid null pointer errors

Summary

Searches for a value in a binary search tree by moving left or right based on comparisons.

Use when you want fast lookup in a sorted tree structure.

The key is to compare and move down the tree, skipping half the nodes each step.

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