Trees

BST Search

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

Algorithm

The canonical tree is 4(2(1,3),6(5,7)), so this R DSA implementation can be compared directly with the rest of the DSA track.

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 = "")

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.