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.