Tree Representations & Recursive vs Iterative Pre/In/Post/Level-Order Traversals

Memory Layouts: Explicit Pointers vs LCRS vs Eytzinger Implicit Arrays

Before analyzing traversal algorithms, a systems engineer must account for the memory footprint and cache behavior of the underlying node representation. In 64-bit architectures, every memory address consumes 8 bytes. A naive binary tree node storing a 64-bit key/payload plus left, right, and parent pointers occupies 32 bytes (plus allocator metadata header overhead of 8–16 bytes), meaning 60% to 75% of L1 cache capacity is spent storing pointers rather than keys.

Four structural representations dominate production systems:

• Tri-Pointer Binary Node (left, right, parent): Requires $3N$ pointers. Out of the $2N$ child pointers in an $N$-node binary tree, exactly $N + 1$ are null (since only $N - 1$ nodes have a parent). The explicit parent pointer enables $O(1)$ amortized tree-walk iteration without an auxiliary stack.
• Bi-Pointer Binary Node (left, right): Strips the parent pointer to save 8 bytes per node, requiring an explicit $O(h)$ stack for upward navigation or ancestor updates.
• Left-Child Right-Sibling (LCRS / Knuth Transform): Encodes an arbitrary $k$-ary tree into a binary tree where node.firstChild points to the leftmost child and node.nextSibling points to the immediate right sibling. This avoids variable-length child vectors (std::vector<Node*>) in DOM trees and ASTs.
• Implicit 1-Indexed Array (Eytzinger / Complete Binary Layout): Places the root at index $1$, with $\text{parent}(i) = \lfloor i/2 \rfloor$, $\text{left}(i) = 2i$, and $\text{right}(i) = 2i + 1$. Requires zero pointers and achieves optimal spatial locality for nearly-complete trees, though sparse skewed trees of height $h$ waste $O(2^h)$ space.

Visualizing the Euler Tour Perimeter Walk

The SVG diagram below traces the continuous Euler contour around a binary tree. Notice how Pre-Order (green entry markers), In-Order (amber underside markers), and Post-Order (purple exit markers) are simply three phase-shifted projections of the exact same walk.

Production Implementations: Iterative Single-Stack Post-Order & Parent-Pointer $O(1)$ Space Walk

While iterative Pre-Order and In-Order are straightforward, single-stack Post-Order requires tracking lastVisited to distinguish returning from a left child versus returning from a right child. Furthermore, if nodes carry a parent pointer (as in std::map / Linux rb_node), we can traverse the entire tree in $O(N)$ time and strict $O(1)$ auxiliary memory without modifying any tree pointers.

// C++20: Single-Stack Iterative Post-Order + O(1) Auxiliary Space Parent-Pointer In-Order
#include <vector>

struct TreeNode {
    int key;
    TreeNode *left = nullptr, *right = nullptr, *parent = nullptr;
};

// 1. Single-Stack Iterative Post-Order (Zero recursion, 8B per active ancestor)
std::vector<int> postorderIterative(const TreeNode* root) {
    std::vector<int> out;
    std::vector<const TreeNode*> st;
    const TreeNode* curr = root;
    const TreeNode* lastVisited = nullptr;

    while (curr != nullptr || !st.empty()) {
        if (curr != nullptr) {
            st.push_back(curr);
            curr = curr->left;
        } else {
            const TreeNode* peek = st.back();
            // If right child exists and we haven't just returned from it, descend right
            if (peek->right != nullptr && lastVisited != peek->right) {
                curr = peek->right;
            } else {
                out.push_back(peek->key);
                lastVisited = peek;
                st.pop_back();
            }
        }
    }
    return out;
}

// 2. O(1) Space In-Order Walk using Parent Pointers (Read-only, thread-safe)
std::vector<int> inorderParentWalk(const TreeNode* root) {
    std::vector<int> out;
    const TreeNode* prev = nullptr;
    const TreeNode* curr = root;

    while (curr != nullptr) {
        const TreeNode* next = nullptr;
        if (prev == curr->parent) {               // Arrived from parent: go left first
            if (curr->left != nullptr) {
                next = curr->left;
            } else {
                out.push_back(curr->key);          // No left subtree: visit In-Order now
                next = (curr->right != nullptr) ? curr->right : curr->parent;
            }
        } else if (prev == curr->left) {           // Returned from left child: visit In-Order
            out.push_back(curr->key);
            next = (curr->right != nullptr) ? curr->right : curr->parent;
        } else {                                   // Returned from right child: ascend
            next = curr->parent;
        }
        prev = curr;
        curr = next;
    }
    return out;
}