Unique Tree Reconstruction (Preorder + Inorder) & Succinct Bit-String Serialization

The Reconstruction Matrix: Which Traversal Pairs Uniquely Identify a Binary Tree?

Assume a binary tree has $N$ distinct keys. When we attempt to reconstruct the tree recursively from two traversal arrays:

• Pre-Order + In-Order (Uniquely Reconstructible in $O(N)$): The first element of Pre-Order is unconditionally the root $r$. Looking up $r$'s index in the In-Order array immediately tells us the exact size $k$ of the left subtree (all elements to the left of $r$) and the size $N - 1 - k$ of the right subtree (all elements to the right of $r$).
• Post-Order + In-Order (Uniquely Reconstructible in $O(N)$): Symmetric—the last element of Post-Order is the root $r$, and In-Order partitions the left and right subtrees.
• Pre-Order + Post-Order (Ambiguous for General Binary Trees!): Pre-Order gives $[r, \text{Left}, \text{Right}]$ and Post-Order gives $[\text{Left}, \text{Right}, r]$. If a node $u$ has only one child $v$, both Pre-Order ($[u, v]$) and Post-Order ($[v, u]$) are identical whether $v$ is a left child or a right child! However, if the tree is a Full (Strict) Binary Tree—where every node has either $0$ or $2$ children—then Pre-Order + Post-Order does uniquely reconstruct the tree because whenever $u$ is not a leaf, the element immediately following $u$ in Pre-Order is guaranteed to be $u$'s left child, and its position in Post-Order marks the exact end of the left subtree.

Visualizing Subtree Partitioning & Succinct Bit Encoding

Implementation: $O(N)$ Hash-Free Boundary Reconstruction & Bitstream Codec

Even without a hash map, we can reconstruct a binary tree from Pre-Order and In-Order in strict $O(N)$ time by passing the upper-bound sentinel key stopVal down the recursion (or using an explicit stack):

// C++20: O(N) Zero-HashMap Reconstruction from Pre-Order + In-Order using Boundary Sentinel
#include <vector>
#include <limits>

struct TreeNode {
    int val;
    TreeNode *left = nullptr, *right = nullptr;
    explicit TreeNode(int v) : val(v) {}
};

class TreeReconstructor {
    size_t preIdx = 0;
    size_t inIdx = 0;

    TreeNode* buildBoundary(const std::vector<int>& pre, const std::vector<int>& in, long long stopVal) {
        if (preIdx >= pre.size()) return nullptr;
        if (in[inIdx] == stopVal) {
            ++inIdx; // Reached the ancestor boundary in In-Order: left/right subtree complete
            return nullptr;
        }
        int rootVal = pre[preIdx++];
        TreeNode* root = new TreeNode(rootVal);
        // Left subtree stops when In-Order hits rootVal
        root->left = buildBoundary(pre, in, rootVal);
        // Right subtree stops when In-Order hits our parent's stopVal
        root->right = buildBoundary(pre, in, stopVal);
        return root;
    }

public:
    TreeNode* buildTree(const std::vector<int>& preorder, const std::vector<int>& inorder) {
        preIdx = 0;
        inIdx = 0;
        return buildBoundary(preorder, inorder, std::numeric_limits<long long>::max());
    }
};