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.

level order Level-order traversal uses a queue to visit shallower nodes first.

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

                        
1tree ← 4(2(1,3),6(5,7)), queue ← [4]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[4]queue
2output ← [4], queue ← [2, 6]⋯8fun listString(values: List<Int>) = values.joinToString(", ", "[", "]")9fun 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)) }values this step[4]output[2, 6]queue4dequeued
3output ← [4, 2], queue ← [6, 1, 3]⋯8fun listString(values: List<Int>) = values.joinToString(", ", "[", "]")9fun 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)) }values this step[4, 2]output[6, 1, 3]queue2dequeued
4output ← [4, 2, 6], queue ← [1, 3, 5, 7]⋯8fun listString(values: List<Int>) = values.joinToString(", ", "[", "]")9fun 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)) }values this step[4, 2, 6]output[1, 3, 5, 7]queue6dequeued
5output ← [4, 2, 6, 1], queue ← [3, 5, 7]⋯8fun listString(values: List<Int>) = values.joinToString(", ", "[", "]")9fun 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)) }values this step[4, 2, 6, 1]output[3, 5, 7]queue1dequeued
6output ← [4, 2, 6, 1, 3], queue ← [5, 7]⋯8fun listString(values: List<Int>) = values.joinToString(", ", "[", "]")9fun 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)) }values this step[4, 2, 6, 1, 3]output[5, 7]queue3dequeued
7output ← [4, 2, 6, 1, 3, 5], queue ← [7]⋯8fun listString(values: List<Int>) = values.joinToString(", ", "[", "]")9fun 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)) }values this step[4, 2, 6, 1, 3, 5]output[7]queue5dequeued
8output ← [4, 2, 6, 1, 3, 5, 7], queue ← []⋯8fun listString(values: List<Int>) = values.joinToString(", ", "[", "]")9fun 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)) }values this step[4, 2, 6, 1, 3, 5, 7]output[]queue7dequeued
9fun main() { val queue = ArrayDeque<Node>(); queue.addLast(sampleTree(…⋯8fun listString(values: List<Int>) = values.joinToString(", ", "[", "]")9fun 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)) }values this step[4, 2, 6, 1, 3, 5, 7]output

Complexity

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

Implementation notes

Kotlin represents nodes with class Node(val value: Int, var left: Node? = null, var right: Node? = null), so child links are nullable references.
sampleTree() allocates the fixed root and children with nested Node(...) constructor calls before traversal starts.
The traversal queue is val queue = ArrayDeque<Node>(); the binding is not rebound, but addLast and removeFirst mutate the queue contents.
The root is enqueued with queue.addLast(sampleTree()), so queue entries are non-null Node references rather than nullable nodes.
while (!queue.isEmpty()) guards queue.removeFirst(), avoiding the empty deque exception path.
Output is collected in val output = mutableListOf<Int>() with output.add(node.value) after each dequeue.
Child enqueue uses null guards: node.left?.let { queue.addLast(it) } and the same for right, preserving left-before-right level order without enqueuing null sentinels.
The trace shows queue/output states [4], then output [4] with queue [2, 6], then [4, 2] with [6, 1, 3], then [4, 2, 6] with [1, 3, 5, 7], ending at [4, 2, 6, 1, 3, 5, 7] and an empty queue.
println(listString(output)) formats the collected values as [4, 2, 6, 1, 3, 5, 7].