Trees

BST Search

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

Algorithm

Basic Implementation

basic.sh 
#!/usr/bin/env bash
declare -A val left right
new_node() { local id=$1 value=$2 l=${3:-0} r=${4:-0}; val[$id]=$value; left[$id]=$l; right[$id]=$r; }
render() {
  local id=$1
  if [[ "$id" == "0" || -z "$id" ]]; then printf "_"; return; fi
  if [[ "${left[$id]}" == "0" && "${right[$id]}" == "0" ]]; then printf "%s" "${val[$id]}"; return; fi
  printf "%s(" "${val[$id]}"; render "${left[$id]}"; printf ","; render "${right[$id]}"; printf ")"
}
sample_tree() {
  new_node 1 1; new_node 3 3; new_node 2 2 1 3
  new_node 5 5; new_node 7 7; new_node 6 6 5 7
  new_node 4 4 2 6
}
list_string() {
  local joined=""
  for value in "$@"; do
    [[ -n "$joined" ]] && joined+=", "
    joined+="$value"
  done
  printf '[%s]' "$joined"
}
sample_tree
search() { local id=4 target=$1; while [[ "$id" != "0" ]]; do if (( target == val[$id] )); then return 0; elif (( target < val[$id] )); then id=${left[$id]}; else id=${right[$id]}; fi; done; return 1; }
search 5 && echo "5 found" || echo "5 not found"
search 8 && echo "8 found" || echo "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.