Build a Binary Tree

Create a fixed seven-node binary tree and render its shape.

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 = ", "), "]")
cat(render(sample_tree()), "\n", sep = "")

Complexity

Time: O(n)
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.

node links A node stores one value plus references to its left and right children.