Construct a Full Binary Tree from Preorder and Mirror Preorder Traversal

C# Corner

Construct a Full Binary Tree from Preorder and Mirror Preorder Traversal

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

Problem Statement

You are given two arrays:

pre[] → Preorder traversal of the original full binary tree.
preMirror[] → Preorder traversal of the mirror of the same tree.

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:

0 children (leaf node), or
2 children (internal node).

This property makes the reconstruction unique.

Understanding the Traversals

Original Tree Preorder

Preorder traversal follows:

Root → Left → Right

Example

Preorder

1 2 4 5 3 6 7

Mirror Tree

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

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:

Root
Right Subtree
Left Subtree

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

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:

root.left
root.right

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:

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

pre → Preorder array
l → Left boundary in mirror preorder
r → Right boundary in mirror preorder

Base Case 1

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

If:

preorder traversal is finished, or
the current range is invalid,

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:

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:

Next node:

Mirror index:

Recursive calls:

Left

build(4,6)

Right

build(1,3)

Left Subtree

Create:

Mirror index:

Build:

4
5

Right Subtree

Create:

Mirror index:

Build:

6
7

Final Tree

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

Complexity Analysis

Time Complexity

Building the HashMap: O(n)
Each node is created exactly once: O(n)

Total Time Complexity: O(n)

Space Complexity

HashMap stores n nodes: O(n)
Recursive call stack (worst case): O(n)

Total Auxiliary Space: O(n)

Key Takeaways

The tree can be reconstructed uniquely because it is a full binary tree.
A HashMap is used to quickly locate nodes in the mirror preorder traversal.
preIndex always points to the next node to create from the preorder array.
The index found in the mirror preorder determines the boundaries for recursively constructing the left and right subtrees.
Every node is processed exactly once, resulting in an O(n) time complexity.

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.