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 Scala 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.scala
                        
Replay: real traced execution (multi-file project)

                            import scala.collection.mutable.{ArrayBuffer, Queue}
class Node(val value: Int, var left: Node = null, var right: Node = null)
object Main {
  def render(node: Node): String = {
    if (node == null) "_"
    else if (node.left == null && node.right == null) node.value.toString
    else s"${node.value}(${render(node.left)},${render(node.right)})"
  }
  def sampleTree(): Node = new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)))
  def listString(values: Seq[Int]): String = values.mkString("[", ", ", "]")
  def main(args: Array[String]): Unit = { val queue = Queue.empty[Node]; queue.enqueue(sampleTree()); val output = ArrayBuffer.empty[Int]; while (queue.nonEmpty) { val node = queue.dequeue(); output += node.value; if (node.left != null) queue.enqueue(node.left); if (node.right != null) queue.enqueue(node.right) }; println(listString(output)) }
}

                        
1tree ← 4(2(1,3),6(5,7)), queue ← [4]1import scala.collection.mutable.{ArrayBuffer, Queue}2class Node(val value: Int, var left: Node = null, var right: Node = null)⋯values this step4(2(1,3),6(5,7))tree[4]queue
2output ← [4], queue ← [2, 6]⋯10  def listString(values: Seq[Int]): String = values.mkString("[", ", ", "]")11  def main(args: Array[String]): Unit = { val queue = Queue.empty[Node]; queue.enqueue(sampleTree()); val output = ArrayBuffer.empty[Int]; while (queue.nonEmpty) { val node = queue.dequeue(); output += node.value; if (node.left != null) queue.enqueue(node.left); if (node.right != null) queue.enqueue(node.right) }; println(listString(output)) }12}values this step[4]output[2, 6]queue4dequeued
3output ← [4, 2], queue ← [6, 1, 3]⋯10  def listString(values: Seq[Int]): String = values.mkString("[", ", ", "]")11  def main(args: Array[String]): Unit = { val queue = Queue.empty[Node]; queue.enqueue(sampleTree()); val output = ArrayBuffer.empty[Int]; while (queue.nonEmpty) { val node = queue.dequeue(); output += node.value; if (node.left != null) queue.enqueue(node.left); if (node.right != null) queue.enqueue(node.right) }; println(listString(output)) }12}values this step[4, 2]output[6, 1, 3]queue2dequeued
4output ← [4, 2, 6], queue ← [1, 3, 5, 7]⋯10  def listString(values: Seq[Int]): String = values.mkString("[", ", ", "]")11  def main(args: Array[String]): Unit = { val queue = Queue.empty[Node]; queue.enqueue(sampleTree()); val output = ArrayBuffer.empty[Int]; while (queue.nonEmpty) { val node = queue.dequeue(); output += node.value; if (node.left != null) queue.enqueue(node.left); if (node.right != null) queue.enqueue(node.right) }; println(listString(output)) }12}values this step[4, 2, 6]output[1, 3, 5, 7]queue6dequeued
5output ← [4, 2, 6, 1], queue ← [3, 5, 7]⋯10  def listString(values: Seq[Int]): String = values.mkString("[", ", ", "]")11  def main(args: Array[String]): Unit = { val queue = Queue.empty[Node]; queue.enqueue(sampleTree()); val output = ArrayBuffer.empty[Int]; while (queue.nonEmpty) { val node = queue.dequeue(); output += node.value; if (node.left != null) queue.enqueue(node.left); if (node.right != null) queue.enqueue(node.right) }; println(listString(output)) }12}values this step[4, 2, 6, 1]output[3, 5, 7]queue1dequeued
6output ← [4, 2, 6, 1, 3], queue ← [5, 7]⋯10  def listString(values: Seq[Int]): String = values.mkString("[", ", ", "]")11  def main(args: Array[String]): Unit = { val queue = Queue.empty[Node]; queue.enqueue(sampleTree()); val output = ArrayBuffer.empty[Int]; while (queue.nonEmpty) { val node = queue.dequeue(); output += node.value; if (node.left != null) queue.enqueue(node.left); if (node.right != null) queue.enqueue(node.right) }; println(listString(output)) }12}values this step[4, 2, 6, 1, 3]output[5, 7]queue3dequeued
7output ← [4, 2, 6, 1, 3, 5], queue ← [7]⋯10  def listString(values: Seq[Int]): String = values.mkString("[", ", ", "]")11  def main(args: Array[String]): Unit = { val queue = Queue.empty[Node]; queue.enqueue(sampleTree()); val output = ArrayBuffer.empty[Int]; while (queue.nonEmpty) { val node = queue.dequeue(); output += node.value; if (node.left != null) queue.enqueue(node.left); if (node.right != null) queue.enqueue(node.right) }; println(listString(output)) }12}values this step[4, 2, 6, 1, 3, 5]output[7]queue5dequeued
8output ← [4, 2, 6, 1, 3, 5, 7], queue ← []⋯10  def listString(values: Seq[Int]): String = values.mkString("[", ", ", "]")11  def main(args: Array[String]): Unit = { val queue = Queue.empty[Node]; queue.enqueue(sampleTree()); val output = ArrayBuffer.empty[Int]; while (queue.nonEmpty) { val node = queue.dequeue(); output += node.value; if (node.left != null) queue.enqueue(node.left); if (node.right != null) queue.enqueue(node.right) }; println(listString(output)) }12}values this step[4, 2, 6, 1, 3, 5, 7]output[]queue7dequeued
9def main(args: Array[String]): Unit = { val queue = Queue.empty[Node];…⋯10  def listString(values: Seq[Int]): String = values.mkString("[", ", ", "]")11  def main(args: Array[String]): Unit = { val queue = Queue.empty[Node]; queue.enqueue(sampleTree()); val output = ArrayBuffer.empty[Int]; while (queue.nonEmpty) { val node = queue.dequeue(); output += node.value; if (node.left != null) queue.enqueue(node.left); if (node.right != null) queue.enqueue(node.right) }; println(listString(output)) }12}values this step[4, 2, 6, 1, 3, 5, 7]output

Complexity

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

Implementation notes

class Node(val value: Int, var left: Node = null, var right: Node = null) is the same mutable-link tree shape used by the neighboring Scala lessons.
Empty child links are checked with node.left != null and node.right != null; this source does not wrap children in Option.
Queue.empty[Node] stores node references for the next visits, and queue.enqueue(sampleTree()) starts the replay at [4].
The loop is iterative: while (queue.nonEmpty) dequeues the front node, appends node.value into ArrayBuffer.empty[Int], then enqueues the left child before the right child.
That enqueue order is visible in the trace: after dequeuing 4, the queue is [2, 6]; after dequeuing 2, it becomes [6, 1, 3].
The full replay drains the queue as 4, 2, 6, 1, 3, 5, 7, ending with an empty queue and output [4, 2, 6, 1, 3, 5, 7].
listString(output) uses mkString("[", ", ", "]"), so println emits the same bracketed level-order list shown in the final trace state.