Articles

Every recursive function over a binary tree visits nodes in some order. The structure itself has no arrows pointing in a straight line: a tree is a value with two smaller trees attached, and moving through it requires a decision at every step. That decision is where pre-order, in-order, and post-order traversals come from. They are not three separate algorithms. They are three distinct views of the exact same recursive process, determined entirely by when you choose to look at the current node relative to its children.

Understanding traversals as views of recursive execution state clarifies both tree problem-solving and pure functional data modeling. This article explores how the call stack manages subtree state, how each order serves a different computational goal, and how pattern matching in Elixir contrasts with pointer manipulation in JavaScript.

The Three Orders: One Walk, Three Perspectives

A binary tree is defined recursively: a tree is either empty (nil or :empty), or a root node containing a value and two subtrees, left and right. To visit every node in a tree, a recursive algorithm must perform three actions:

Process the current node ( $N$ ).
Recursively traverse the left subtree ( $L$ ).
Recursively traverse the right subtree ( $R$ ).

The relative placement of step 1 produces the three classic depth-first traversal orders:

Pre-order ( $N \to L \to R$ ): Process the parent first, before either child.
In-order ( $L \to N \to R$ ): Process the parent in between the left and right subtrees.
Post-order ( $L \to R \to N$ ): Process the parent last, after both children are fully resolved.

Each ordering corresponds to a specific algorithmic role:

Pre-Order: Parent First, Prefix Notation, and Serialization

In pre-order traversal, a node is inspected the moment the traversal enters it. Because the parent is recorded before its subtrees, pre-order captures the structural hierarchy from top to bottom.

This makes pre-order ideal for serialization and cloning. When saving a tree to a flat string or list, writing the parent before the children allows a deserializer to reconstruct the exact same root and branches without ambiguity (provided empty leaves are marked). Pre-order is also the order of mathematical prefix expressions: in an expression tree for (3 + 5) * 2, the pre-order traversal yields * + 3 5 2.

When solving problems like Invert Binary Tree, pre-order thinking allows you to swap a node’s left and right pointers immediately before descending into them, propagating structural mutations downward from the root.

In-Order: The Sorted Projection of a BST

In-order traversal visits the entire left subtree, yields the current node, and then visits the right subtree.

On an arbitrary binary tree, in-order provides a left-to-right spatial projection. On a Binary Search Tree (BST), where the left subtree holds only values strictly less than the node and the right subtree holds values strictly greater, in-order traversal yields values in monotonically increasing, sorted order.

This property makes in-order the fundamental tool for inspecting and verifying BST invariants. If an in-order walk of a candidate tree produces any pair where current <= previous, the tree is not a valid BST. Solving Binary Tree Inorder Traversal demonstrates this walk directly.

Post-Order: Bottom-Up Aggregation, Evaluation, and Destruction

In post-order traversal, the algorithm does not process a node until both of its subtrees have returned their results. This is the natural order for bottom-up aggregation.

If you need to calculate a property of a node that depends on its children - such as height, subtree weight, or diameter - you cannot compute the answer until the recursive calls on left and right finish. For example, in Maximum Depth of Binary Tree, the depth of any node is 1 + max(depth(left), depth(right)). The addition of 1 happens strictly after both subtrees report their depths.

Post-order is also the order of post-fix expression evaluation (Reverse Polish Notation) and memory deallocation in manual memory management systems, where child nodes must be freed before their parent pointer is destroyed.

In Lowest Common Ancestor of a Binary Search Tree, analyzing subtrees bottom-up or guiding descent based on subtree value ranges allows finding the shared divergence point in $O(h)$ time.

Recursion as Stack Frames: Call Stack vs. Accumulator State

When writing a recursive traversal, the call stack tracks the state of the walk. Each invocation of the traversal function places a new frame on the runtime stack.

Consider traversing this tree in-order:

When execution begins at root 4, the function does not process 4 yet. It pushes traverse(4) onto the call stack and immediately calls traverse(2). At 2, it pushes traverse(2) and calls traverse(1). At 1, it calls traverse(nil) on the empty left child, which returns immediately. Only then does 1 get emitted.

At this exact moment, the call stack holds the pending chain of parent contexts:

| traverse(1) - emitting 1, about to visit right child
| traverse(2) - waiting for left subtree to complete
| traverse(4) - waiting for left subtree to complete
+---------------------------------------------------

The call stack functions as an implicit memory buffer that remembers where to resume once child subtrees finish.

In imperative code, converting a recursive traversal to an iterative loop requires explicitly pushing node pointers onto a heap-allocated Stack data structure to mimic these exact stack frames.

In pure functional programming, we often write traversals using either direct tree recursion or an accumulator-passing style:

# Direct recursion: returns a new list by combining subtree lists
def inorder_list(nil), do: []
def inorder_list(%TreeNode{val: v, left: l, right: r}) do
  inorder_list(l) ++ [v] ++ inorder_list(r)
end

# Tail-recursive accumulator: passes the collected result downward
def inorder_acc(root), do: do_inorder_acc(root, [])

defp do_inorder_acc(nil, acc), do: acc
defp do_inorder_acc(%TreeNode{val: v, left: l, right: r}, acc) do
  # In order to collect L, V, R into acc, we process right subtree first,
  # then prepend V, then process left subtree.
  acc_after_right = do_inorder_acc(r, acc)
  do_inorder_acc(l, [v | acc_after_right])
end

In inorder_acc/2, notice the inversion: to produce [1, 2, 3, 4, 5] efficiently using list prepends ([head | tail]), the accumulator visits the right subtree first, adds v, and feeds that accumulator into the traversal of the left subtree. The accumulator threads state across the traversal without needing list concatenations (++).

Tree Invariants in Pure FP: Pattern Matching vs. Pointer Mutation

In JavaScript and TypeScript, binary trees are typically represented as mutable class instances or object references with nullable properties:

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

// In-place mutation during traversal (e.g. tree inversion)
function invertTree(root: TreeNode | null): TreeNode | null {
  if (root === null) return null;

  const temp = root.left;
  root.left = invertTree(root.right);
  root.right = invertTree(temp);

  return root;
}

In this JavaScript example, invertTree modifies the existing node objects in-place via reference reassignment (root.left = ...). While memory-efficient, pointer mutation introduces risks: shared references across asynchronous tasks or concurrent operations can lead to subtle race conditions and unintended mutations.

In Elixir and functional languages on the BEAM, tree structures are immutable maps or structs. Instead of mutating pointer fields, operations use pattern matching to deconstruct the tree and construct a new tree sharing unchanged subtrees:

defmodule TreeNode do
  defstruct val: 0, left: nil, right: nil
  @type t :: %TreeNode{val: integer(), left: t() | nil, right: t() | nil}
end

defmodule TreeTransform do
  # Pure structural transformation: pattern matching enforces completeness
  def invert_tree(nil), do: nil

  def invert_tree(%TreeNode{val: v, left: l, right: r}) do
    %TreeNode{
      val: v,
      left: invert_tree(r),
      right: invert_tree(l)
    }
  end
end

Pattern matching against %TreeNode{val: v, left: l, right: r} separates traversal logic from mutation. The base case nil and the recursive case %TreeNode{} are handled cleanly as pattern clauses.

Because data is immutable, returning a new %TreeNode{} does not copy the entire tree. Unmodified subtrees are shared in memory between the old and new tree versions. The compiler and runtime guarantee that no other process can alter the tree while a traversal is running.

Where to go next

Binary Tree Inorder Traversal - practice implementing the in-order walk across languages and observing the sorted projection of nodes.
Invert Binary Tree - apply pre-order and post-order recursive restructuring to mirror a tree’s left and right branches.
Maximum Depth of Binary Tree - see bottom-up post-order aggregation in action by computing subtree depths.
Lowest Common Ancestor of a Binary Search Tree - use BST search properties and path descent to find the split point between two target values.
Binary trees: where the log in O(log n) lives - the foundational article on binary tree structure, tree height, and the doubling argument.
Recursion: the pattern that calls itself - how call frames are created and unwound during recursive execution.