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.

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

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.
level order Level-order traversal uses a queue to visit shallower nodes first.