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.

Basic Implementation

basic.scala

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)) }
}

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.

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