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:
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
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:
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:
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
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.