Trees

BST Insert

Insert values into a binary search tree by comparing at each node.

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 = ", "), "]")
insert <- function(root, value) { if (is.null(root)) return(node(value)); if (value < root$value) root$left <- insert(root$left, value) else root$right <- insert(root$right, value); root }
root <- NULL
for (value in c(4, 2, 6, 1, 3, 5, 7)) root <- insert(root, value)
cat(render(root), "\n", sep = "")

Complexity

  • Time: O(h) per insert
  • Space: O(n)

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.
binary search tree Values smaller than a node go left; larger values go right.