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.

Basic Implementation

basic.kt 
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)) }

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].
preorder Preorder records the current node before visiting left and right subtrees.