Trees

BST Insert

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

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

BST insertion is a comparison path. The pinned tree 4(2(1,3),6(5,7)) is shown with the inserted value taking its sorted slot.

Step 1 - Start at root

For value 5, compare with 4 first; 5 is larger, so move right.

First comparison: 5 > 4, so the search for the insert slot goes right.insert 54compare26137

Step 2 - Take the left slot under 6

At 6, value 5 is smaller, so it becomes the left child.

Second comparison: 5 < 6, so the open left slot is used.426compare135new7

Step 3 - Canonical tree

The resulting tree is the pinned shape 4(2(1,3),6(5,7)).

Final BST after 5 is present under 6.4261357

Complexity

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

Implementation notes

  • node <- function(value, left = NULL, right = NULL) list(...) builds each tree node as an R list with value, left, and right fields.
  • The code reads and mutates those fields with $, such as root$value, root$left, and root$right.
  • root starts as NULL. When insert(root, value) sees a NULL root, it returns node(value), so the loop must write the return value back with root <- insert(root, value).
  • The pinned insertion order is c(4, 2, 6, 1, 3, 5, 7).
  • if (value < root$value) recurses left; the else branch recurses right. After assigning root$left or root$right, insert() returns root.

Replay steps

4: root
2: 4 -> left
6: 4 -> right
1: 4 -> left -> 2 -> left
final: 4(2(1,3),6(5,7))
  • render() prints _ for NULL, a bare character value for a leaf, and value(left,right) for an internal node.
  • cat(render(root), "\n", sep = "") prints the canonical tree 4(2(1,3),6(5,7)).
  • The trace keeps the imbalance contrast: sorted inserts [1, 2, 3, 4] form 1(_,2(_,3(_,4))), a height-4 chain with O(n) search/insert cost when no rotation step is present.
binary search tree Values smaller than a node go left; larger values go right.