1. Mathematical Definition & Traversal Taxonomy

Depth-first tree traversal algorithms are classified according to the relative order in which the root node is visited relative to its left and right subtrees:

• Pre-Order (Root → Left → Right): Used for serializing/cloning trees and evaluating prefix mathematical expressions.
• In-Order (Left → Root → Right): Used for sorted extraction of BST keys and infix algebraic parsing.
• Post-Order (Left → Right → Root): Used for bottom-up cleanup, directory disk usage computation, and postfix (Reverse Polish) evaluation.

The core invariant of in-order traversal guarantees that for any subtree rooted at node $N$, all nodes in $N$'s left subtree are visited before $N$, and all nodes in $N$'s right subtree are visited after $N$.

2. Method 1: The Recursive Approach (Call Stack Mechanics)

The recursive implementation is intuitive and declarative. In languages with call-by-value semantics (Java, TypeScript, C++), the runtime allocates a new activation frame on the thread's call stack for every recursive function invocation.

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

// Recursive In-Order Traversal
export function inorderRecursive(root: TreeNode | null): number[] {
  const result: number[] = [];

  function traverse(node: TreeNode | null): void {
    if (!node) return;
    traverse(node.left);       // 1. Traverse left subtree
    result.push(node.val);     // 2. Visit root
    traverse(node.right);      // 3. Traverse right subtree
  }

  traverse(root);
  return result;
}

Complexity Analysis:

• Time Complexity: $mathcal{O}(N)$, where $N$ is the total number of nodes in the binary tree. Every node is visited exactly once.
• Auxiliary Space Complexity: $mathcal{O}(H)$, where $H$ is the height of the tree. For a balanced binary tree, $H = log_2 N$. However, in a pathological worst-case scenario (a skewed, degenerate tree resembling a linked list), $H = N$. On large trees ($N > 10^5$), deep recursion exhausts stack limits, throwing fatal StackOverflowError in Java or RangeError: Maximum call stack size exceeded in Node.js.

3. Method 2: Iterative Traversal with an Explicit Stack

To guard against call stack exhaustion, production systems convert recursion into an iterative loop backed by an explicit stack allocated on the system heap. Memory allocated on the heap is bounded only by available RAM, avoiding rigid thread stack limits.

// Iterative In-Order Traversal using Heap-Allocated LIFO Stack
export function inorderIterative(root: TreeNode | null): number[] {
  const result: number[] = [];
  const stack: TreeNode[] = [];
  let current: TreeNode | null = root;

  while (current !== null || stack.length > 0) {
    // Traverse left as far as possible, pushing nodes onto the stack
    while (current !== null) {
      stack.push(current);
      current = current.left;
    }

    // Current is now null; pop the most recent node from the stack
    current = stack.pop()!;
    result.push(current.val);

    // Pivot to the right subtree
    current = current.right;
  }

  return result;
}

This implementation guarantees determinism and graceful memory scaling, making it the standard choice for enterprise AST parsers and graph query engines.

4. Method 3: Morris Traversal ($O(1)$ Auxiliary Space)

In 1979, Joseph M. Morris published an algorithm capable of traversing a binary tree in in-order sequence without recursion and without using an external stack. Instead of storing parent links in auxiliary memory, Morris Traversal utilizes unused null right-child pointers in the tree to create temporary threads pointing back to ancestor nodes.

The algorithm follows these precise steps:

1. Initialize current = root.
2. While current is not null:
   • If current.left is null: Visit current and move to current.right.
   • Else, find the in-order predecessor of current (the rightmost node in current's left subtree):
     • If predecessor.right is null: Establish thread by setting predecessor.right = current, then advance current = current.left.
     • If predecessor.right === current: The thread was already established, meaning the left subtree has been completely visited. Remove thread (predecessor.right = null), visit current, and advance current = current.right.

// Morris In-Order Traversal: O(N) Time, True O(1) Auxiliary Space
export function inorderMorris(root: TreeNode | null): number[] {
  const result: number[] = [];
  let current: TreeNode | null = root;

  while (current !== null) {
    if (current.left === null) {
      result.push(current.val);
      current = current.right;
    } else {
      // Find in-order predecessor
      let predecessor: TreeNode = current.left;
      while (predecessor.right !== null && predecessor.right !== current) {
        predecessor = predecessor.right;
      }

      if (predecessor.right === null) {
        // Step 1: Establish temporary thread
        predecessor.right = current;
        current = current.left;
      } else {
        // Step 2: Thread encountered; left subtree complete, remove thread
        predecessor.right = null;
        result.push(current.val);
        current = current.right;
      }
    }
  }

  return result;
}

5. Comparative Engineering Trade-Off Matrix

Selecting the optimal traversal algorithm depends on the operational constraints of the runtime environment:

In concurrent microservices where read-locks are shared, iterative traversal provides the safest guarantee. In memory-constrained microcontrollers or massive graph processing jobs where auxiliary memory cannot be spared, Morris Traversal stands as one of computer science's most elegant algorithmic feats.