Trees

BST Search

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

Algorithm

Basic Implementation

basic.R 
node <- function(value, left = NULL, right = NULL) list(value = value, left = left, right = right)
render <- function(n) {
  if (is.null(n)) return("_")
  if (is.null(n$left) && is.null(n$right)) return(as.character(n$value))
  paste0(n$value, "(", render(n$left), ",", render(n$right), ")")
}
sample_tree <- function() node(4, node(2, node(1), node(3)), node(6, node(5), node(7)))
list_string <- function(values) paste0("[", paste(values, collapse = ", "), "]")
search <- function(root, target) { n <- root; while (!is.null(n)) { if (target == n$value) return(TRUE); n <- if (target < n$value) n$left else n$right }; FALSE }
root <- sample_tree()
cat(if (search(root, 5)) "5 found" else "5 not found", "\n", sep = "")
cat(if (search(root, 8)) "8 found" else "8 not found", "\n", sep = "")

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

  • sample_tree() builds the canonical list-node tree 4(2(1,3),6(5,7)).
  • Each node is an R list with value, left, and right fields, read as n$value, n$left, and n$right.
  • search <- function(root, target) is iterative. It starts with n <- root and keeps looping while !is.null(n).
  • The loop checks target == n$value first. A match returns TRUE immediately.
  • Otherwise the cursor moves with n <- if (target < n$value) n$left else n$right.
  • If the cursor falls off the tree to NULL, the loop ends and the function returns FALSE.

Replay steps

target 5: 4 -> right, 6 -> left, 5 -> match
target 8: 4 -> right, 6 -> right, 7 -> right, NULL -> not found
  • Those cursor moves skip whole branches: searching for 5 never visits the 2(1,3) side, and searching for 8 only follows the right edge.
  • The two cat(...) calls print exactly:
5 found
8 not found
search path A comparison chooses one subtree at each step, so whole branches are skipped.