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.