Trees

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 Kotlin 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.kt
Replay: real traced execution (multi-file project)
class Node(val value: Int, var left: Node? = null, var right: Node? = null)
fun render(node: Node?): String {
    if (node == null) return "_"
    if (node.left == null && node.right == null) return node.value.toString()
    return "${node.value}(${render(node.left)},${render(node.right)})"
}
fun sampleTree() = Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))
fun listString(values: List<Int>) = values.joinToString(", ", "[", "]")
fun preorder(node: Node?, output: MutableList<Int>) { if (node == null) return; output.add(node.value); preorder(node.left, output); preorder(node.right, output) }
fun main() { val output = mutableListOf<Int>(); preorder(sampleTree(), output); println(listString(output)) }

  1. tree ← 4(2(1,3),6(5,7)), output ← []

    1class Node(val value: Int, var left: Node? = null, var right: Node? = null)2fun render(node: Node?): String {
    values this step4(2(1,3),6(5,7))tree[]output

  2. output ← [4]

    8fun listString(values: List<Int>) = values.joinToString(", ", "[", "]")9fun preorder(node: Node?, output: MutableList<Int>) { if (node == null) return; output.add(node.value); preorder(node.left, output); preorder(node.right, output) }10fun main() { val output = mutableListOf<Int>(); preorder(sampleTree(), output); println(listString(output)) }
    values this step[] → [4]output4node

  3. output ← [4, 2]

    8fun listString(values: List<Int>) = values.joinToString(", ", "[", "]")9fun preorder(node: Node?, output: MutableList<Int>) { if (node == null) return; output.add(node.value); preorder(node.left, output); preorder(node.right, output) }10fun main() { val output = mutableListOf<Int>(); preorder(sampleTree(), output); println(listString(output)) }
    values this step[4] → [4, 2]output2node

  4. output ← [4, 2, 1]

    8fun listString(values: List<Int>) = values.joinToString(", ", "[", "]")9fun preorder(node: Node?, output: MutableList<Int>) { if (node == null) return; output.add(node.value); preorder(node.left, output); preorder(node.right, output) }10fun main() { val output = mutableListOf<Int>(); preorder(sampleTree(), output); println(listString(output)) }
    values this step[4, 2] → [4, 2, 1]output1node

  5. output ← [4, 2, 1, 3]

    8fun listString(values: List<Int>) = values.joinToString(", ", "[", "]")9fun preorder(node: Node?, output: MutableList<Int>) { if (node == null) return; output.add(node.value); preorder(node.left, output); preorder(node.right, output) }10fun main() { val output = mutableListOf<Int>(); preorder(sampleTree(), output); println(listString(output)) }
    values this step[4, 2, 1] → [4, 2, 1, 3]output3node

  6. output ← [4, 2, 1, 3, 6]

    8fun listString(values: List<Int>) = values.joinToString(", ", "[", "]")9fun preorder(node: Node?, output: MutableList<Int>) { if (node == null) return; output.add(node.value); preorder(node.left, output); preorder(node.right, output) }10fun main() { val output = mutableListOf<Int>(); preorder(sampleTree(), output); println(listString(output)) }
    values this step[4, 2, 1, 3] → [4, 2, 1, 3, 6]output6node

  7. output ← [4, 2, 1, 3, 6, 5]

    8fun listString(values: List<Int>) = values.joinToString(", ", "[", "]")9fun preorder(node: Node?, output: MutableList<Int>) { if (node == null) return; output.add(node.value); preorder(node.left, output); preorder(node.right, output) }10fun main() { val output = mutableListOf<Int>(); preorder(sampleTree(), output); println(listString(output)) }
    values this step[4, 2, 1, 3, 6] → [4, 2, 1, 3, 6, 5]output5node

  8. output ← [4, 2, 1, 3, 6, 5, 7]

    8fun listString(values: List<Int>) = values.joinToString(", ", "[", "]")9fun preorder(node: Node?, output: MutableList<Int>) { if (node == null) return; output.add(node.value); preorder(node.left, output); preorder(node.right, output) }10fun main() { val output = mutableListOf<Int>(); preorder(sampleTree(), output); println(listString(output)) }
    values this step[4, 2, 1, 3, 6, 5] → [4, 2, 1, 3, 6, 5, 7]output7node

  9. fun main() { val output = mutableListOf<Int>(); preorder(sampleTree(),…

    9fun preorder(node: Node?, output: MutableList<Int>) { if (node == null) return; output.add(node.value); preorder(node.left, output); preorder(node.right, output) }10fun main() { val output = mutableListOf<Int>(); preorder(sampleTree(), output); println(listString(output)) }
    values this step[4, 2, 1, 3, 6, 5, 7]output

Complexity

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

Implementation notes

  • Kotlin represents nodes with class Node(val value: Int, var left: Node? = null, var right: Node? = null), so recursive calls must handle nullable child references.
  • sampleTree() allocates the fixed tree with nested Node(...) constructor calls before traversal starts.
  • The traversal function is preorder(node: Node?, output: MutableList<Int>); it mutates the caller-owned output list instead of returning a new list.
  • if (node == null) return is the base case for missing children, so no null sentinel is added to the output.
  • For a real node, output.add(node.value) happens before preorder(node.left, output) and preorder(node.right, output), giving root-left-right order.
  • main creates val output = mutableListOf<Int>(), calls preorder(sampleTree(), output), then formats the same list.
  • The trace records visits 4, 2, 1, 3, 6, 5, 7, with output growing from [] to [4, 2, 1, 3, 6, 5, 7].
  • println(listString(output)) prints [4, 2, 1, 3, 6, 5, 7].