Trees

Preorder Traversal

Visit the root before each subtree, producing root-left-right order.

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 = ", "), "]")
preorder <- function(n) { if (is.null(n)) return(c()); c(n$value, preorder(n$left), preorder(n$right)) }
cat(list_string(preorder(sample_tree())), "\n", sep = "")

Complexity

  • Time: O(n)
  • Space: O(h) recursion stack

Implementation notes

  • sample_tree() builds the fixed tree 4(2(1,3),6(5,7)).
  • The traversal is the recursive function preorder <- function(n) { if (is.null(n)) return(c()); c(n$value, preorder(n$left), preorder(n$right)) }.
  • The base case returns c() for a NULL child, so missing children add no values to the final vector.
  • The c(...) expression shows the order directly: n$value first, then the recursive left vector, then the recursive right vector.

Replay steps

visit 4: [4]
visit 2: [4, 2]
visit 1: [4, 2, 1]
visit 3: [4, 2, 1, 3]
visit 6: [4, 2, 1, 3, 6]
visit 5: [4, 2, 1, 3, 6, 5]
visit 7: [4, 2, 1, 3, 6, 5, 7]
  • list_string(preorder(sample_tree())) formats [4, 2, 1, 3, 6, 5, 7], and cat(..., "\n", sep = "") prints that exact line.
preorder Preorder records the current node before visiting left and right subtrees.