Module 17 · Binary Trees: Recursive DFS and Structural Contracts

163. Recursive Preorder Traversal

Foundation · Download this solution · All solutions and shared helpers

Problem

Return the values of a binary tree in recursive preorder: root, left subtree, right subtree. Empty input returns []. Preserve duplicate values and visit every node occurrence once. Leave the tree unchanged.

Examples

Example 1

preorder(build_tree([1,2,3,4]))
=> [1, 2, 4, 3]

The entire left subtree follows its parent before the right subtree.

Example 2

preorder(None)
=> []

An empty subtree emits nothing.

Example 3

preorder(build_tree([2,2,2]))
=> [2, 2, 2]

Equal-valued node occurrences are distinct visits.

Reveal the worked solution and reasoning

Why this mechanism works

Traversal order is controlled by when the current node's value is emitted relative to child calls. Preorder emits before either delegation, so a parent always precedes all of its descendants. A shared append-only output avoids the repeated list copying of concatenated recursive results.

State and boundaries

visit(node) appends the complete preorder sequence of that subtree. output already holds all earlier traversal events.

Protocol

Return immediately for None.
Append the current value.
Visit the left subtree.
Visit the right subtree.

Visualization

    1
   / \
  2   3
preorder events: emit 1 -> emit 2 -> emit 3

Python implementation

from structures import build_tree

def preorder(root):
    output = []
    def visit(node):
        if node is None:
            return
        output.append(node.val)
        visit(node.left)
        visit(node.right)
    visit(root)
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

preorder(build_tree([1,2,3,4]))

L4 preorder: output = []
root=N1(val=1,left=N2,right=N3); output=[]

L6 visit: if node is None:
node=N1(val=1,left=N2,right=N3); output=[]

L8 visit: output.append(node.val)
node=N1(val=1,left=N2,right=N3); output=[1]

L6 visit: if node is None:
node=N2(val=2,left=N4,right=None); output=[1]

L8 visit: output.append(node.val)
node=N2(val=2,left=N4,right=None); output=[1, 2]

L6 visit: if node is None:
node=N4(val=4,left=None,right=None); output=[1, 2]

L8 visit: output.append(node.val)
node=N4(val=4,left=None,right=None); output=[1, 2, 4]

L6 visit: if node is None:
node=None; output=[1, 2, 4]

... 6 intermediate state changes omitted ...

L6 visit: if node is None:
node=None; output=[1, 2, 4, 3]

L6 visit: if node is None:
node=None; output=[1, 2, 4, 3]

L10 visit: visit(node.right)
node=N1(val=1,left=N2,right=N3); output=[1, 2, 4, 3]

L11 preorder: visit(root)
root=N1(val=1,left=N2,right=N3); output=[1, 2, 4, 3]

Result: [1, 2, 4, 3]. The entire left subtree follows its parent before the right subtree.

preorder(None)

L4 preorder: output = []
root=None; output=[]

L6 visit: if node is None:
node=None; output=[]

Result: []. An empty subtree emits nothing.

Why the solution is correct

For an empty subtree no values are appended. For a real node, the append followed by correct left and right child traversals is exactly root-left-right order. By structural induction the root call produces the complete preorder. Every recursive call descends into a finite child subtree.

Time and space

O(n) time, O(n) output space and O(h) recursive stack space.

Common mistakes

Appending after visiting a child changes the traversal. Treating equal values as already visited would incorrectly omit distinct nodes.

Reasoning card

State: visit(node) appends the complete preorder sequence of that subtree. output already holds all earlier traversal events.

Invariant: Output contains the preorder of completed subtrees.

Decision to rehearse: Process current node before child calls.

Finish: Visit the right subtree

Transfer exercise

Write iterative preorder. Explain why a LIFO stack must receive the right child before the left child.