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.

preorder Preorder records the current node before visiting left and right subtrees.

Basic Implementation

basic.R
Replay: real traced execution (multi-file project)
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 = "")

  1. tree ← 4(2(1,3),6(5,7)), output ← []

    1node <- function(value, left = NULL, right = NULL) list(value = value, left = left, right = right)2render <- function(n) {
    values this step4(2(1,3),6(5,7))tree[]output

  2. output ← [4]

    8list_string <- function(values) paste0("[", paste(values, collapse = ", "), "]")9preorder <- function(n) { if (is.null(n)) return(c()); c(n$value, preorder(n$left), preorder(n$right)) }10cat(list_string(preorder(sample_tree())), "\n", sep = "")
    values this step[] → [4]output4node

  3. output ← [4, 2]

    8list_string <- function(values) paste0("[", paste(values, collapse = ", "), "]")9preorder <- function(n) { if (is.null(n)) return(c()); c(n$value, preorder(n$left), preorder(n$right)) }10cat(list_string(preorder(sample_tree())), "\n", sep = "")
    values this step[4] → [4, 2]output2node

  4. output ← [4, 2, 1]

    8list_string <- function(values) paste0("[", paste(values, collapse = ", "), "]")9preorder <- function(n) { if (is.null(n)) return(c()); c(n$value, preorder(n$left), preorder(n$right)) }10cat(list_string(preorder(sample_tree())), "\n", sep = "")
    values this step[4, 2] → [4, 2, 1]output1node

  5. output ← [4, 2, 1, 3]

    8list_string <- function(values) paste0("[", paste(values, collapse = ", "), "]")9preorder <- function(n) { if (is.null(n)) return(c()); c(n$value, preorder(n$left), preorder(n$right)) }10cat(list_string(preorder(sample_tree())), "\n", sep = "")
    values this step[4, 2, 1] → [4, 2, 1, 3]output3node

  6. output ← [4, 2, 1, 3, 6]

    8list_string <- function(values) paste0("[", paste(values, collapse = ", "), "]")9preorder <- function(n) { if (is.null(n)) return(c()); c(n$value, preorder(n$left), preorder(n$right)) }10cat(list_string(preorder(sample_tree())), "\n", sep = "")
    values this step[4, 2, 1, 3] → [4, 2, 1, 3, 6]output6node

  7. output ← [4, 2, 1, 3, 6, 5]

    8list_string <- function(values) paste0("[", paste(values, collapse = ", "), "]")9preorder <- function(n) { if (is.null(n)) return(c()); c(n$value, preorder(n$left), preorder(n$right)) }10cat(list_string(preorder(sample_tree())), "\n", sep = "")
    values this step[4, 2, 1, 3, 6] → [4, 2, 1, 3, 6, 5]output5node

  8. output ← [4, 2, 1, 3, 6, 5, 7]

    8list_string <- function(values) paste0("[", paste(values, collapse = ", "), "]")9preorder <- function(n) { if (is.null(n)) return(c()); c(n$value, preorder(n$left), preorder(n$right)) }10cat(list_string(preorder(sample_tree())), "\n", sep = "")
    values this step[4, 2, 1, 3, 6, 5] → [4, 2, 1, 3, 6, 5, 7]output7node

  9. cat(list_string(preorder(sample_tree())), " ", sep = "")

    9preorder <- function(n) { if (is.null(n)) return(c()); c(n$value, preorder(n$left), preorder(n$right)) }10cat(list_string(preorder(sample_tree())), "\n", sep = "")
    values this step[4, 2, 1, 3, 6, 5, 7]output

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.