Trees

BST Search

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

Algorithm

Basic Implementation

basic.sql 
SELECT '5 found';
SELECT '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

  • Render tree structure explicitly instead of printing node objects.
  • The replay highlights the node, traversal state, queue, path, or search cursor that changes at each step.
search path A comparison chooses one subtree at each step, so whole branches are skipped.