700. Search in a Binary Search Tree

Approach

What is This Problem?

Given the root of a Binary Search Tree (BST) and a value val, return the node with that value, or null if not found.

In a BST, for any node:

• All values in the left subtree are less than the node’s value.
• All values in the right subtree are greater than the node’s value.

Why This Works

A BST’s ordering property allows us to eliminate half of the remaining tree at each step, similar to binary search on a sorted array. By comparing val with the current node’s value, we can decide whether to continue searching in the left subtree (if val is smaller) or the right subtree (if val is larger). This makes the search O(h) where h is tree height (O(log n) for balanced tree).

The provided solution performs a full binary tree traversal, which works but takes O(n) time in worst case. The efficient BST search would use the ordering to prune branches.

Algorithm Steps

1. Start at the root.
2. While current node is not null:
   • If val === current.val, return current node.
   • If val < current.val, move to left child.
   • If val > current.val, move to right child.
3. If we reach a null pointer, the value is not in the tree → return null.

Visualization

Consider BST:

      4
     / \
    2   7
   / \
  1   3

Search for val = 3:

Step 1: At root 4 → 3 < 4 → go left Step 2: At node 2 → 3 > 2 → go right Step 3: At node 3 → found!

Search path: 4 → 2 → 3

Another example: Search for 5 (not present): 4 → (5 > 4) → 7 → (5 < 7) → left child is null → return null

Key Pattern

• BST property navigation: Left for less, right for greater.
• Iterative or recursive traversal guided by comparisons.
• Early termination when value found.
• Pruning: Discard entire subtrees based on comparison.

When to Use This Pattern

• Searching in any BST (used in many problems like validating BST, inserting, deleting)
• When you have a sorted data structure with tree-based layout
• Problems requiring efficient lookups, min/max queries (min is leftmost, max is rightmost)
• Adaptable to range queries (find all values between low and high)

Solution

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

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

const treeNode4 = new TreeNode(4);
const treeNode2 = new TreeNode(2);
const treeNode7 = new TreeNode(7);
const treeNode1 = new TreeNode(1);
const treeNode3 = new TreeNode(3);

treeNode4.left = treeNode2;
treeNode4.right = treeNode7;
treeNode2.left = treeNode1;
treeNode2.right = treeNode3;

console.log(searchBST(treeNode4, 2));