Trees

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 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 main() { val queue = ArrayDeque<Node>(); queue.addLast(sampleTree()); val output = mutableListOf<Int>(); while (!queue.isEmpty()) { val node = queue.removeFirst(); output.add(node.value); node.left?.let { queue.addLast(it) }; node.right?.let { queue.addLast(it) } }; println(listString(output)) }

Complexity

  • Time: O(n)
  • Space: O(w) queue space

Implementation notes

  • Render tree structure explicitly instead of printing node objects.
  • The replay highlights the node, traversal state, queue, path, or search cursor that changes at each step.
level order Level-order traversal uses a queue to visit shallower nodes first.