Trees

BST Search

Search a binary search tree for one present and one absent value.

Algorithm

Basic Implementation

basic.ts 
class Node {
  value: number;
  left: Node | null;
  right: Node | null;
  constructor(value: number, left: Node | null = null, right: Node | null = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}
function render(node: Node | null): string {
  if (node === null) return "_";
  if (node.left === null && node.right === null) return String(node.value);
  return `${node.value}(${render(node.left)},${render(node.right)})`;
}
function sampleTree(): Node {
  return new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));
}

const root = sampleTree();
function search(root, target) { let node = root; while (node !== null) { if (target === node.value) return true; node = target < node.value ? node.left : node.right; } return false; }
console.log(search(root, 5) ? "5 found" : "5 not found");
console.log(search(root, 8) ? "8 found" : "8 not found");

A BST search follows one comparison path. The same pinned tree shows a found path for 5 and a missing path for 8.

Step 1 - Find 5

Search 5 takes right from 4, then left from 6, then matches 5.

Present search path: 4 -> 6 -> 5.4#126#2135match7

Step 2 - Miss 8

Search 8 takes right from 4, right from 6, right from 7, then reaches null.

Absent search path: 4 -> 6 -> 7 -> null.4#126#21357#3nullnot found

Complexity

  • Time: O(h) per search
  • Space: O(1) iterative

Implementation notes

  • Node is a TypeScript class with value: number, left: Node | null, and right: Node | null fields. The sample tree stores missing children as null.
  • The compact search(root, target) helper in the checked source omits parameter annotations, but it traverses Node | null references and numeric targets.
  • Search is iterative: let node = root holds the cursor, and while (node !== null) stops when traversal falls off the tree.
  • target === node.value returns true on a match. Otherwise target < node.value ? node.left : node.right chooses the next nullable reference using numeric comparison.
  • The replay searches 5 through 4 -> right, 6 -> left, then 5 -> match. It searches 8 through 4 -> right, 6 -> right, 7 -> right, then reaches null and returns false.
  • The two console.log calls print 5 found and 8 not found. Visible allocation is the seven-node sample tree and output strings; the search does not mutate nodes and only reassigns the cursor.
search path A comparison chooses one subtree at each step, so whole branches are skipped.