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 Scala 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.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 preorder(node: Node, output: ArrayBuffer[Int]): Unit = { if (node == null) return; output += node.value; preorder(node.left, output); preorder(node.right, output) }
  def main(args: Array[String]): Unit = { val output = ArrayBuffer.empty[Int]; preorder(sampleTree(), output); println(listString(output)) }
}

                        
1tree ← 4(2(1,3),6(5,7)), output ← []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[]output
2output ← [4]⋯10def listString(values: Seq[Int]): String = values.mkString("[", ", ", "]")11def preorder(node: Node, output: ArrayBuffer[Int]): Unit = { if (node == null) return; output += node.value; preorder(node.left, output); preorder(node.right, output) }12def main(args: Array[String]): Unit = { val output = ArrayBuffer.empty[Int]; preorder(sampleTree(), output); println(listString(output)) }⋯values this step[] → [4]output4node
3output ← [4, 2]⋯10def listString(values: Seq[Int]): String = values.mkString("[", ", ", "]")11def preorder(node: Node, output: ArrayBuffer[Int]): Unit = { if (node == null) return; output += node.value; preorder(node.left, output); preorder(node.right, output) }12def main(args: Array[String]): Unit = { val output = ArrayBuffer.empty[Int]; preorder(sampleTree(), output); println(listString(output)) }⋯values this step[4] → [4, 2]output2node
4output ← [4, 2, 1]⋯10def listString(values: Seq[Int]): String = values.mkString("[", ", ", "]")11def preorder(node: Node, output: ArrayBuffer[Int]): Unit = { if (node == null) return; output += node.value; preorder(node.left, output); preorder(node.right, output) }12def main(args: Array[String]): Unit = { val output = ArrayBuffer.empty[Int]; preorder(sampleTree(), output); println(listString(output)) }⋯values this step[4, 2] → [4, 2, 1]output1node
5output ← [4, 2, 1, 3]⋯10def listString(values: Seq[Int]): String = values.mkString("[", ", ", "]")11def preorder(node: Node, output: ArrayBuffer[Int]): Unit = { if (node == null) return; output += node.value; preorder(node.left, output); preorder(node.right, output) }12def main(args: Array[String]): Unit = { val output = ArrayBuffer.empty[Int]; preorder(sampleTree(), output); println(listString(output)) }⋯values this step[4, 2, 1] → [4, 2, 1, 3]output3node
6output ← [4, 2, 1, 3, 6]⋯10def listString(values: Seq[Int]): String = values.mkString("[", ", ", "]")11def preorder(node: Node, output: ArrayBuffer[Int]): Unit = { if (node == null) return; output += node.value; preorder(node.left, output); preorder(node.right, output) }12def main(args: Array[String]): Unit = { val output = ArrayBuffer.empty[Int]; preorder(sampleTree(), output); println(listString(output)) }⋯values this step[4, 2, 1, 3] → [4, 2, 1, 3, 6]output6node
7output ← [4, 2, 1, 3, 6, 5]⋯10def listString(values: Seq[Int]): String = values.mkString("[", ", ", "]")11def preorder(node: Node, output: ArrayBuffer[Int]): Unit = { if (node == null) return; output += node.value; preorder(node.left, output); preorder(node.right, output) }12def main(args: Array[String]): Unit = { val output = ArrayBuffer.empty[Int]; preorder(sampleTree(), output); println(listString(output)) }⋯values this step[4, 2, 1, 3, 6] → [4, 2, 1, 3, 6, 5]output5node
8output ← [4, 2, 1, 3, 6, 5, 7]⋯10def listString(values: Seq[Int]): String = values.mkString("[", ", ", "]")11def preorder(node: Node, output: ArrayBuffer[Int]): Unit = { if (node == null) return; output += node.value; preorder(node.left, output); preorder(node.right, output) }12def main(args: Array[String]): Unit = { val output = ArrayBuffer.empty[Int]; preorder(sampleTree(), output); println(listString(output)) }⋯values this step[4, 2, 1, 3, 6, 5] → [4, 2, 1, 3, 6, 5, 7]output7node
9def main(args: Array[String]): Unit = { val output = ArrayBuffer.empty…⋯11  def preorder(node: Node, output: ArrayBuffer[Int]): Unit = { if (node == null) return; output += node.value; preorder(node.left, output); preorder(node.right, output) }12  def main(args: Array[String]): Unit = { val output = ArrayBuffer.empty[Int]; preorder(sampleTree(), output); println(listString(output)) }13}values this step[4, 2, 1, 3, 6, 5, 7]output

Complexity

Time: O(n)
Space: O(h) recursion stack

Implementation notes

class Node(val value: Int, var left: Node = null, var right: Node = null) keeps the tree as mutable child references with an immutable Int value.
Empty branches are plain null links, and preorder stops each empty branch with if (node == null) return.
preorder(node: Node, output: ArrayBuffer[Int]): Unit mutates one shared ArrayBuffer instead of returning a new list from each call.
The visit happens before either child call: output += node.value, then preorder(node.left, output), then preorder(node.right, output).
That left-before-right recursion is visible in the replay as 4, 2, 1, 3, then 6, 5, 7.
The trace shows the output growing one slot at a time, ending at [4, 2, 1, 3, 6, 5, 7].
listString(output) formats the ArrayBuffer with mkString("[", ", ", "]"), so println emits that exact bracketed preorder list.