Trees

Level-Order Traversal

Visit a tree breadth-first with a queue.

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.

level order Level-order traversal uses a queue to visit shallower nodes first.

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 = ", "), "]")
queue <- list(sample_tree())
output <- c()
while (length(queue) > 0) { n <- queue[[1]]; queue <- queue[-1]; output <- c(output, n$value); if (!is.null(n$left)) queue <- append(queue, list(n$left)); if (!is.null(n$right)) queue <- append(queue, list(n$right)) }
cat(list_string(output), "\n", sep = "")

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

    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[4]queue

  2. output ← [4], queue ← [2, 6]

    8list_string <- function(values) paste0("[", paste(values, collapse = ", "), "]")9queue <- list(sample_tree())10output <- c()
    values this step[4]output[2, 6]queue4dequeued

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

    8list_string <- function(values) paste0("[", paste(values, collapse = ", "), "]")9queue <- list(sample_tree())10output <- c()
    values this step[4, 2]output[6, 1, 3]queue2dequeued

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

    8list_string <- function(values) paste0("[", paste(values, collapse = ", "), "]")9queue <- list(sample_tree())10output <- c()
    values this step[4, 2, 6]output[1, 3, 5, 7]queue6dequeued

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

    8list_string <- function(values) paste0("[", paste(values, collapse = ", "), "]")9queue <- list(sample_tree())10output <- c()
    values this step[4, 2, 6, 1]output[3, 5, 7]queue1dequeued

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

    8list_string <- function(values) paste0("[", paste(values, collapse = ", "), "]")9queue <- list(sample_tree())10output <- c()
    values this step[4, 2, 6, 1, 3]output[5, 7]queue3dequeued

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

    8list_string <- function(values) paste0("[", paste(values, collapse = ", "), "]")9queue <- list(sample_tree())10output <- c()
    values this step[4, 2, 6, 1, 3, 5]output[7]queue5dequeued

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

    8list_string <- function(values) paste0("[", paste(values, collapse = ", "), "]")9queue <- list(sample_tree())10output <- c()
    values this step[4, 2, 6, 1, 3, 5, 7]output[]queue7dequeued

  9. cat(list_string(output), " ", sep = "")

    11while (length(queue) > 0) { n <- queue[[1]]; queue <- queue[-1]; output <- c(output, n$value); if (!is.null(n$left)) queue <- append(queue, list(n$left)); if (!is.null(n$right)) queue <- append(queue, list(n$right)) }12cat(list_string(output), "\n", sep = "")
    values this step[4, 2, 6, 1, 3, 5, 7]output

Complexity

  • Time: O(n)
  • Space: O(w) queue space

Implementation notes

  • sample_tree() builds the fixed tree 4(2(1,3),6(5,7)).
  • queue <- list(sample_tree()) stores tree nodes in an R list used as a FIFO queue, and output <- c() starts the visited-value vector.
  • while (length(queue) > 0) keeps running while there are nodes waiting.
  • n <- queue[[1]] reads the front node, and queue <- queue[-1] removes that first queue slot.
  • output <- c(output, n$value) records the visited node value.
  • Non-NULL children are enqueued with append(queue, list(n$left)) and append(queue, list(n$right)).
  • The list(child) wrapper matters: it appends the whole child node as one queue item instead of flattening its fields into the queue.

Replay steps

start:   queue [4], output []
visit 4: queue [2, 6], output [4]
visit 2: queue [6, 1, 3], output [4, 2]
visit 6: queue [1, 3, 5, 7], output [4, 2, 6]
finish:  queue [], output [4, 2, 6, 1, 3, 5, 7]
  • list_string(output) formats [4, 2, 6, 1, 3, 5, 7], and cat(..., "\n", sep = "") prints that exact line.