Construct a Full Binary Tree from Preorder and Mirror Preorder Traversal (Java)

Problem Statement

You are given two arrays:

Your task is to construct the original full binary tree.

Note: The tree is guaranteed to be a Full Binary Tree, which means every node has either:

This property makes the reconstruction unique.

Understanding the Traversals

Original Tree Preorder

Preorder traversal follows:

Root → Left → Right

Example

        1
      /   \
     2     3
    / \   / \
   4  5  6  7

Preorder

1 2 4 5 3 6 7

Mirror Tree

A mirror tree swaps every left child with its right child.

        1
      /   \
     3     2
    / \   / \
   7  6  5  4

Mirror preorder also follows:

Root → Left → Right

So the mirror preorder becomes:

1 3 7 6 2 5 4

Key Observation

The first element of both arrays is always the root.

pre

1 2 4 5 3 6 7
^

preMirror

1 3 7 6 2 5 4
^

So,

Root = 1

What Comes Next?

The second element in preorder is always the left child.

pre

1 2 4 5 3 6 7
  ^

So,

Left Child = 2

Now search this node in the mirror preorder.

preMirror

1 3 7 6 2 5 4
        ^

Node 2 is found at index 4.

This index helps determine where the left subtree begins and ends.

Why Does This Work?

Mirror preorder visits nodes in the following order:

When we find node 2, everything before it belongs to the right subtree.

Everything from index 4 onward belongs to the left subtree.

This allows us to recursively construct the tree.

Step-by-Step Algorithm

Step 1

Store every element of preMirror inside a HashMap.

Value → Index

1 → 0
3 → 1
7 → 2
6 → 3
2 → 4
5 → 5
4 → 6

This lets us find any node in O(1) time.

Step 2

Maintain one global variable:

preIndex

Initially,

preIndex = 0

It always points to the next node to create.

Step 3

Create the root.

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

Increment:

preIndex++;

Step 4

If only one node exists:

l == r

Return the node.

It is a leaf node.

Step 5

Otherwise, find the next preorder element inside the mirror preorder.

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

This tells us where the left subtree starts.

Step 6

Recursively construct:

Complete Code

class Solution {

    HashMap<Integer, Integer> map;
    int preIndex;

    public Node constructBinaryTree(int[] pre, int[] preMirror) {

        map = new HashMap<>();

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

        preIndex = 0;

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

    private Node build(int[] pre, 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, idx, r);

        root.right = build(pre, l + 1, idx - 1);

        return root;
    }
}

Line-by-Line Explanation

Variables

HashMap<Integer, Integer> map;

Stores:

Node Value → Index in Mirror Preorder

Example:

2 → 4
6 → 3
7 → 2

This avoids repeated searching, making each lookup O(1).

int preIndex;

Tracks the next node in preorder.

Initially,

preIndex = 0

constructBinaryTree()

map = new HashMap<>();

Creates the HashMap.

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

Stores every node with its index.

Example:

1 → 0
3 → 1
7 → 2
6 → 3
2 → 4

preIndex = 0;

Start from the first preorder element.

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

Construct the complete tree.

build()

private Node build(int[] pre, int l, int r)

Parameters

Base Case 1

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

If:

stop recursion.

Create Current Node

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

Example:

pre

1 2 4 5 3 6 7
^

Create node 1.

Increment preIndex.

Now:

1 2 4 5 3 6 7
  ^

Base Case 2

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

Only one node exists.

So it is a leaf node.

Return immediately.

Find Left Child

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

Suppose:

pre

1 2 4 5 3 6 7
  ^

Next node:

2

Mirror

1 3 7 6 2 5 4
        ^

Therefore,

idx = 4

Build Left Subtree

root.left = build(pre, idx, r);

Constructs the left subtree.

Build Right Subtree

root.right = build(pre, l + 1, idx - 1);

Constructs the right subtree.

Return

return root;

Returns the completed subtree.

Complete Dry Run

Input

pre

1 2 4 5 3 6 7

preMirror

1 3 7 6 2 5 4

Call 1

preIndex = 0

Create:

1

Next node:

2

Mirror index:

4

Recursive calls:

Left

build(4,6)

Right

build(1,3)

Left Subtree

Create:

2

Next:

4

Mirror index:

6

Build:

4
5

Right Subtree

Create:

3

Next:

6

Mirror index:

3

Build:

6
7

Final Tree

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

Complexity Analysis

Time Complexity

Total Time Complexity: O(n)

Space Complexity

Total Auxiliary Space: O(n)

Key Takeaways

Summary

A full binary tree can be uniquely reconstructed using its preorder traversal and the preorder traversal of its mirror. By storing mirror preorder indices in a HashMap and maintaining a single preorder pointer, the algorithm efficiently identifies subtree boundaries and recursively builds the original tree. Since each node is processed exactly once and every lookup is performed in constant time, the overall time complexity is O(n) with O(n) auxiliary space.