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.

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

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.

preorder Preorder records the current node before visiting left and right subtrees.