Tree traversals visit the same nodes in different orders. Pre-order processes the current node before its children, in-order processes it between the left and right children, and post-order processes it after them. The recording traces these choices and also introduces breadth-first traversal. The order should follow what your algorithm needs from each node.
Put the visit at the right point
Consider a root 2 with left child 1 and right child 3. Pre-order gives 2, 1, 3. In-order gives 1, 2, 3. Post-order gives 1, 3, 2. The recursive structure can remain the same while the placement of the processing step changes the result.
In-order visits values in ascending order only when the tree satisfies the binary search tree ordering. An arbitrary binary tree with those same three positions can produce an unsorted sequence. A traversal defines when a node is visited; it does not change the values or enforce an ordering property.
Match traversal order to dependencies
Pre-order is useful when a parent must be processed before descendants. Post-order supports calculations that need completed child results, such as deriving a subtree height. In-order can inspect ordered keys in a binary search tree. These examples describe dependencies rather than rules that one traversal is universally better.
Breadth-first traversal uses a queue to visit one depth before the next. Start by checking for an empty root; the corrected code returns before trying to read missing node fields. If your input can contain shared descendants or cycles, it is no longer the simple tree assumed by these routines and needs explicit graph-style visitation rules.
Account for the unfinished work
A traversal that visits every node takes linear time under bounded per-node work. Recursive auxiliary space follows tree height. A queue-based breadth-first traversal can retain a whole wide level. Any returned list also occupies linear space and should be counted separately from the traversal's worklist.
Use the tree traversal tool to compare the orders on one shape. Then draw a one-sided chain and a wide tree to compare memory needs. Continue with Binary Tree Max Depth and explain why a parent combines completed child results even though the input links point from parent to child.
Work through an in-order traversal
The example uses the same heap-indexed nullable slots as the tree-height example: left is 2i + 1 and right is 2i + 2. For [8, 3, 10, null, 6], the returned order is [3, 6, 8, 10]. Visiting left, then node, then right produces that result. Moving the node visit before or after its child calls produces pre-order or post-order instead.
A null parent ends the branch. A later numeric slot does not become reachable merely because it exists in the array. This is a representation contract, so do not copy a compact breadth-first serialization into the function and assume the positions mean the same thing.
Explain what the order guarantees
In-order traversal returns sorted values only when the tree satisfies the binary-search ordering rule. An arbitrary binary tree still has a valid in-order traversal, but its output need not be sorted. That distinction keeps traversal mechanics separate from tree invariants.
The function visits each reachable node once, for O(r) time, and returns O(r) values. Recursion contributes O(h) active frames for height h. A long chain can exhaust the host call stack even though the algorithm is linear. Include empty, singleton, left-only, right-only, and duplicate-payload shapes in your checks. Duplicates do not change how traversal follows links.
Swift example and implementation choices
guard let extracts a payload or exits the branch, keeping nil distinct from zero. The nested helper captures the output array and appends between child calls. Swift Array provides the integer positions this representation expects; the same arithmetic would not apply directly to String or an arbitrary Collection. The returned Array value contains every reachable payload once in in-order sequence.
Worked example
func inOrder(_ values: [Int?]) -> [Int] {
var output: [Int] = []
func walk(_ index: Int) {
if index >= values.count { return }
guard let value = values[index] else { return }
walk(2 * index + 1)
output.append(value)
walk(2 * index + 2)
}
walk(0)
return output
}
Continue in Swift
Open Tree Traversal: In-Order, Pre-Order, Post-Order for the complete course explanation. The course keeps your saved programming-language choice. Use this standalone page to inspect the Swift example and run it in your own local environment. Follow the original course sequence when you want the surrounding lesson context and related exercises.
The Swift interview preparation guide connects these language choices with further practice and the cross-language operation reference.