BST Search Operation in DSA Javascript

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 name in a phone book by opening to the middle, then deciding to go to the left or right half depending on the name.

      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->8] -> 3 -> 10 -> 1 -> 6 -> 14 -> 4 -> 7 -> 13

Why: We always start searching from the root

Step 2: Compare 7 with 8, move left to node 3 because 7 < 8

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

Why: 7 is less than 8, so it must be in left subtree if it exists

Step 3: Compare 7 with 3, move right to node 6 because 7 > 3

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

Why: 7 is greater than 3, so it must be in right subtree

Step 4: Compare 7 with 6, move right to node 7 because 7 > 6

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

Why: 7 is greater than 6, so move right

Step 5: Compare 7 with 7, found the value

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

Why: Current node value matches search value, stop search

Result:

8 -> 3 -> 6 -> 7 -> null
Value 7 found in BST

Annotated Code

DSA Javascript

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BST {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const newNode = new Node(value);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    let curr = this.root;
    while (true) {
      if (value < curr.value) {
        if (!curr.left) {
          curr.left = newNode;
          return;
        }
        curr = curr.left; // move left
      } else {
        if (!curr.right) {
          curr.right = newNode;
          return;
        }
        curr = curr.right; // move right
      }
    }
  }

  search(value) {
    let curr = this.root;
    while (curr) {
      if (value === curr.value) {
        return true; // found
      } else if (value < curr.value) {
        curr = curr.left; // move left
      } else {
        curr = curr.right; // move right
      }
    }
    return false; // not found
  }

  printInOrder(node = this.root) {
    if (!node) return '';
    let left = this.printInOrder(node.left);
    let right = this.printInOrder(node.right);
    return (left ? left + ' -> ' : '') + node.value + (right ? ' -> ' + right : '');
  }
}

// Driver code
const bst = new BST();
[8,3,10,1,6,14,4,7,13].forEach(v => bst.insert(v));
const searchValue = 7;
const found = bst.search(searchValue);
console.log(bst.printInOrder() + ' -> null');
console.log(`Value ${searchValue} ${found ? 'found' : 'not found'} in BST`);

let curr = this.root;

start search from root node

if (value === curr.value) { return true; }

check if current node matches search value

else if (value < curr.value) { curr = curr.left; }

move left if search value is smaller

else { curr = curr.right; }

move right if search value is larger

Output

1 -> 3 -> 4 -> 6 -> 7 -> 8 -> 10 -> 13 -> 14 -> null

Value 7 found in BST

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 few pointers, no extra storage

vs Alternative: Compared to searching in an unsorted list O(n), BST search is faster if tree is balanced

Edge Cases

Empty tree

Search returns false immediately

DSA Javascript

let curr = this.root;

Value not in tree

Search moves down until null and returns false

DSA Javascript

while (curr) { ... } return false;

Value is root node

Search finds value immediately at root

DSA Javascript

if (value === curr.value) { return true; }

When to Use This Pattern

When you need to quickly find if a value exists in a sorted tree structure, use BST search because it skips half the nodes each step.

Common Mistakes

Mistake: Not moving left or right correctly based on comparison
Fix: Always compare and move left if smaller, right if larger

Mistake: Not checking for null before accessing node
Fix: Use while loop condition to stop at null

Summary

Searches for a value in a binary search tree by comparing and moving left or right.

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

The key is to compare and decide direction at each node, skipping half the tree.

Practice

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

easy

A. To insert a new value into the BST

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

C. To delete a value from the BST

D. To balance the BST

Solution

1. Step 1: Understand the search operation

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

2. Step 2: Differentiate from other operations

   Insertion adds new values, deletion removes values, and balancing adjusts the tree structure. Search only checks for existence.

3. Final Answer:

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

4. Quick Check:

   Search = Find value [OK]

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

Common Mistakes:

• Confusing search with insert or delete
• Thinking search changes the tree
• Assuming search balances the tree

2. Which of the following is the correct syntax to start a search function for a BST node in JavaScript?

easy

A. function searchBST(value, root) { }

B. function searchBST(value) { return root; }

C. function searchBST(root) { return value; }

D. function searchBST(root, value) { }

Solution

1. Step 1: Identify parameters needed for BST search

   The search needs the root node to start and the value to find, so parameters are (root, value).

2. Step 2: Check function signature correctness

   function searchBST(root, value) { } correctly uses (root, value). Options A, C, and D have wrong parameter order or missing parameters.

3. Final Answer:

   function searchBST(root, value) { } -> Option D

4. Quick Check:

   Correct parameters order = function searchBST(root, value) { } [OK]

Hint: Root node first, value second in search function [OK]

Common Mistakes:

• Swapping parameter order
• Missing one parameter
• Returning wrong variable immediately

3. Consider the following BST and the search code snippet:

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

const root = new Node(10);
root.left = new Node(5);
root.right = new Node(15);

function searchBST(root, val) {
  if (!root) return false;
  if (root.val === val) return true;
  if (val < root.val) return searchBST(root.left, val);
  else return searchBST(root.right, val);
}

console.log(searchBST(root, 15));

What will be the output?

medium

A. true

B. false

C. undefined

D. Error

Solution

1. Step 1: Trace the search for value 15

   Start at root (10). Since 15 > 10, move to right child (15).

2. Step 2: Check if current node value matches 15

   Node value is 15, which matches the search value, so return true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Value found = true [OK]

Hint: Compare value with node, go left or right [OK]

Common Mistakes:

• Returning false too early
• Not checking node value before recursion
• Confusing left and right child directions

4. The following code is intended to search a value in a BST but does not work correctly. What is the error?

function searchBST(root, val) {
  if (root === null) return false;
  if (root.val === val) return true;
  if (val > root.val) return searchBST(root.left, val);
  else return searchBST(root.right, val);
}

medium

A. Incorrect return type

B. Missing base case for empty tree

C. The comparison directions for left and right child are swapped

D. Function parameters are wrong

Solution

1. Step 1: Analyze comparison logic for recursion

   If val > root.val, search should go right, but code goes left. This is reversed.

2. Step 2: Confirm correct child direction for BST search

   For val > root.val, search right subtree; for val < root.val, search left subtree.

3. Final Answer:

   The comparison directions for left and right child are swapped -> Option C

4. Quick Check:

   Left/right child direction swapped = The comparison directions for left and right child are swapped [OK]

Hint: Greater value goes right, smaller goes left [OK]

Common Mistakes:

• Swapping left and right child in recursion
• Forgetting base case
• Returning wrong data type

5. You have a BST with nodes: 20 (root), 10 (left child), 30 (right child), 5 (left of 10), 15 (right of 10). You want to search for value 12. Which nodes will the search visit in order?

hard

A. 20 -> 10 -> 15

B. 20 -> 30 -> 15

C. 20 -> 10 -> 5

D. 20 -> 15 -> 10

Solution

1. Step 1: Start at root node 20 and compare with 12

   Since 12 < 20, move to left child 10.

2. Step 2: Compare 12 with node 10

   12 > 10, so move to right child 15.

3. Step 3: Compare 12 with node 15

   12 < 15, so move to left child, which is null (not in tree), search ends.

4. Final Answer:

   20 -> 10 -> 15 -> Option A

5. Quick Check:

   Visited nodes = 20, 10, 15 [OK]

Hint: Go left if smaller, right if bigger, stop if null [OK]

Common Mistakes:

• Visiting wrong child nodes
• Assuming 12 is in the tree
• Skipping nodes in path