Construct a Full Binary Tree

Problem Overview

A general binary tree is not unique from preorder alone, but a full binary tree (0 or 2 children) is uniquely fixed by its preorder together with the preorder of its mirror.

Intuition

A general binary tree is not unique from preorder alone, but a full binary tree (0 or 2 children) is uniquely fixed by its preorder together with the preorder of its mirror. Mirror preorder visits root, then original right, then original left - so the next value in original pre (start of the left subtree) appears later in preMirror and splits that range into left and right subtrees.

Algorithm

1Map every preMirror value to its index for O(1) lookups.
2Recursively build with a shared preIndex into pre and a current [l, r] window in preMirror.
3Create the root from pre[preIndex++]. If the window is a single node (or pre is exhausted), return the leaf.
4Let idx = map[pre[preIndex]] - position of the upcoming left-subtree root inside preMirror.
5Build left on [idx, r] and right on [l+1, idx−1] (sides swapped relative to mirror order).
6Return the constructed root.

Example Walkthrough

Input: pre = [1, 2, 4, 5, 3, 6, 7], preMirror = [1, 3, 7, 6, 2, 5, 4]

1. Root = 1. Next pre value is 2, found at index 4 in preMirror.
2. Left of 1 uses preMirror[4..6] = [2,5,4]; right uses preMirror[1..3] = [3,7,6].
3. Recursing yields left subtree 2→(4,5) and right subtree 3→(6,7).

Output: tree with root 1, left 2 (children 4,5), right 3 (children 6,7)

Common Pitfalls

• Left/right ranges from preMirror are swapped versus original order - that is intentional for the mirror.
• preIndex must be shared across recursive calls (instance field or by-reference), not reset per call.
• Works only because the tree is full; a general binary tree would be ambiguous.
• Values are unique; the HashMap index lookup assumes no duplicates.

Construct a Full Binary Tree.java

Java


import java.util.*;

//Structure of Binary Tree Node
class Node {

    int data;
    Node left, right;

    Node(int val) {
        data = val;
        left = right = null;
    }
}

class Solution {

    // Approach: A full binary tree is uniquely determined by its preorder and the
    // preorder of its mirror. Consume nodes from pre in order; look up the next
    // pre value in preMirror to split the current mirror-range into original left
    // (mirror right half) and original right (mirror left half), then recurse.
    // Complexity: O(n) time and O(n) space for the index map and recursion.
    int preIndex = 0;

    public Node constructBinaryTree(int[] pre, int[] preMirror) {
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < preMirror.length; i++) {
            map.put(preMirror[i], i);
        }

        return build(pre, preMirror, map, 0, preMirror.length - 1);
    }

    private Node build(int[] pre, int[] preMirror,
            HashMap<Integer, Integer> map,
            int l, int r) {

        if (preIndex >= pre.length || l > r) {
            return null;
        }

        Node root = new Node(pre[preIndex++]);

        if (l == r || preIndex >= pre.length) {
            return root;
        }

        int idx = map.get(pre[preIndex]);

        root.left = build(pre, preMirror, map, idx, r);
        root.right = build(pre, preMirror, map, l + 1, idx - 1);

        return root;
    }
}

Was this solution helpful?