Inorder produces [1,2,3]. It is sorted because this tree satisfies the BST ordering invariant. Inorder on an arbitrary binary tree has no sorting guarantee.

def traversal_orders(root):
    preorder, inorder, postorder = [], [], []
    def visit(node):
        if node is None:
            return
        value, left, right = node
        preorder.append(value)
        visit(left)
        inorder.append(value)
        visit(right)
        postorder.append(value)
    visit(root)
    return preorder, inorder, postorder

tree = (2, (1, None, None), (3, None, None))
assert traversal_orders(tree) == ([2, 1, 3], [1, 2, 3], [1, 3, 2])
assert traversal_orders(None) == ([], [], [])

Preorder fits work that introduces a node or sends information downward. Postorder fits work that needs completed child results, such as height or deleting an entire owned subtree. Inorder is especially useful with the additional BST ordering property. Level order instead uses BFS and exposes depth layers.

Each node contributes constant work to each list: O(n) time, O(h) stack space, and O(n) output space. An iterative preorder can push right before left on a stack to visit left first. Iterative postorder needs to remember whether a frame is entering or finishing, because a stack of node names alone does not encode that event.

For a serialization, preorder values alone are not enough to preserve an arbitrary binary tree’s shape. Add explicit null markers or another shape representation. Otherwise a left-only and right-only child can produce the same value sequence.

Analogy limit: choosing traversal order does not determine the problem’s full algorithm. You still need a contract for the information passed and produced.

No. Recursively mirror child subtrees and exchange their positions. The transformation changes what you return or mutate during a visit, not the underlying recursion principles.