Module 17 · Binary Trees: Recursive DFS and Structural Contracts

164. Recursive Inorder Traversal

Foundation · Download this solution · All solutions and shared helpers

Problem

Return a binary tree's values in recursive inorder: left subtree, root, right subtree. No binary-search-tree ordering is assumed. Return [] for an empty tree and preserve all node occurrences without mutation.

Examples

Example 1

inorder(build_tree([2,3,1]))
=> [3, 2, 1]

The traversal follows structure, not numerical sorting.

Example 2

inorder(build_tree([2,1,3]))
=> [1, 2, 3]

A valid BST does yield sorted inorder.

Example 3

inorder(None)
=> []

The empty tree has no traversal events.

Reveal the worked solution and reasoning

Why this mechanism works

Move the emission between the two child calls. The left call must finish before the parent value is appended; the right call starts afterward. Inorder becomes sorted only when the input satisfies the BST property. The traversal algorithm itself works on arbitrary binary trees.

State and boundaries

visit(node) appends the complete inorder of its subtree; each frame waits for its left child before emitting its own value.

Protocol

Ignore None.
Visit left.
Append the current value.
Visit right.

Visualization

    2
   / \
  3   1
inorder: 3 -> 2 -> 1
this tree is not a BST, so output is not sorted

Python implementation

from structures import build_tree

def inorder(root):
    output = []
    def visit(node):
        if node is None:
            return
        visit(node.left)
        output.append(node.val)
        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.

inorder(build_tree([2,3,1]))

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

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

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

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

L9 visit: output.append(node.val)
node=N2(val=3,left=None,right=None); output=[3]

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

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

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

... 2 intermediate state changes omitted ...

L9 visit: output.append(node.val)
node=N3(val=1,left=None,right=None); output=[3, 2, 1]

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

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

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

Result: [3, 2, 1]. The traversal follows structure, not numerical sorting.

inorder(build_tree([2,1,3]))

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

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

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

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

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

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

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

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

... 2 intermediate state changes omitted ...

L9 visit: output.append(node.val)
node=N3(val=3,left=None,right=None); output=[1, 2, 3]

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

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

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

Result: [1, 2, 3]. A valid BST does yield sorted inorder.

Why the solution is correct

The base emits the empty sequence. Assuming each child emits its own correct inorder, placing the current value between those sequences gives exactly left-root-right order. This inductive composition covers every node once and terminates on missing children.

Time and space

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

Common mistakes

Expecting sorted output from an arbitrary tree confuses a traversal rule with a data-ordering invariant. Appending before the left call gives preorder instead.

Reasoning card

State: visit(node) appends the complete inorder of its subtree; each frame waits for its left child before emitting its own value.

Invariant: For a BST, emitted values are nondecreasing.

Decision to rehearse: Place the current-node action between child calls.

Finish: Visit right

Transfer exercise

Simulate recursion with a stack that stores ancestors whose left descent is unfinished or whose value has not yet been emitted.