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.
Python example and implementation choices
The nested walk helper captures both values and the output list. It appends after the left call and before the right call, requiring no global accumulator. is None distinguishes missing slots from zero payloads. The returned list is a traversal sequence, not an automatically sorted result. Its order depends on shape unless the caller also establishes the BST invariant.
Worked example
from typing import Optional
def in_order(values: list[Optional[int]]) -> list[int]:
output = []
def walk(index):
if index >= len(values) or values[index] is None:
return
walk(2 * index + 1)
output.append(values[index])
walk(2 * index + 2)
walk(0)
return output
Continue in Python
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 Python 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 Python interview preparation guide connects these language choices with further practice and the cross-language operation reference.