Given only the visiting order of nodes, can we rebuild the original tree? Learn Preorder + Inorder, Postorder + Inorder, splitting logic, recursive algorithms and complete C code through simple examples.
What Does Construct Binary Tree from Traversals Mean?
In the previous traversal chapter, we started with a tree and wrote down its Preorder, Inorder or Postorder sequence. In this chapter, we do the opposite: the sequences are already given, and our job is to draw the correct Binary Tree.
Think of a puzzle. Preorder tells us which node starts a subtree. Postorder tells us which node ends a subtree. Inorder tells us exactly which nodes belong to the left and right parts.
Forward Problem
Given the tree → calculate its traversal output. Example: draw a Binary Tree, then print its Inorder.
Reverse Problem
Given traversal outputs → rebuild the tree shape. This is called reconstruction.
Traversal Rules Needed Before Reconstruction
| Traversal | Visiting Rule | Useful Clue |
|---|---|---|
| Preorder | Root → Left → Right | The first value is the root of the current subtree |
| Inorder | Left → Root → Right | Values to the left and right of the root identify its subtrees |
| Postorder | Left → Right → Root | The last value is the root of the current subtree |
Inorder is like a boundary marker. Once we know a root, we find that value in Inorder. Everything before it is in the left subtree. Everything after it is in the right subtree. Then we apply the same idea recursively.
Construct Binary Tree from Preorder and Inorder Traversal
Suppose we are given these two traversal sequences. We want to build the only Binary Tree that produces both outputs.
Step 1: Choose the Main Root
The first value of Preorder is A. Therefore, A must be the root of the entire tree. Find A in Inorder to divide the remaining values.
Left subtree: D, B, E | Root: A | Right subtree: F, C, G
Step 2: Reconstruct the Left Subtree
Three nodes are on the left in Inorder, so the next three Preorder values belong to the left subtree: B D E. Its root is B because B appears first in that Preorder portion.
Find B in the left Inorder portion D B E: D is on the left of B and E is on its right. So B has left child D and right child E.
Step 3: Reconstruct the Right Subtree
Remaining Preorder = C F G. Remaining Inorder = F C G. The first Preorder value C becomes the right-subtree root. In Inorder, F is before C and G is after C. Therefore C has left child F and right child G.
Step 4: Join Both Subtrees to A
Preorder + Inorder Reconstruction Dry Run
| Call | Preorder Part | Inorder Part | Root Found |
|---|---|---|---|
| Whole tree | A B D E C F G | D B E A F C G | A |
| A's left | B D E | D B E | B |
| B's left | D | D | D |
| B's right | E | E | E |
| A's right | C F G | F C G | C |
| C's left | F | F | F |
| C's right | G | G | G |
Algorithm for Preorder + Inorder
BUILD_PRE_IN(inLeft, inRight):
IF inLeft > inRight: RETURN NULL
rootValue = preorder[preIndex]
preIndex = preIndex + 1
root = new Node(rootValue)
split = position of rootValue in inorder
root.left = BUILD_PRE_IN(inLeft, split - 1)
root.right = BUILD_PRE_IN(split + 1, inRight)
RETURN root
Construct Binary Tree from Postorder and Inorder Traversal
Now we are given the Inorder and Postorder sequences of the same seven-node tree. The method is similar, but one important detail changes: Postorder's last node is the root.
- Take the last Postorder value A. This is the root.
- Find A in Inorder. Left part: D B E. Right part: F C G.
- The right subtree has three nodes, and its Postorder portion is F G C. Its root is C, the last value of that portion.
- In Inorder F C G, F is left of C and G is right of C. Attach F and G.
- Then use the left Postorder portion D E B. Its root is B. In Inorder D B E, D is left and E is right.
- Attach B and C under A. The result matches the tree in Figure 2.
Postorder + Inorder Reconstruction Dry Run
| Action | Postorder Portion | Inorder Portion | Selected Root |
|---|---|---|---|
| Start | D E B F G C A | D B E A F C G | A |
| Build A's right | F G C | F C G | C |
| C's right, then left | G, then F | G, then F | G, then F |
| Build A's left | D E B | D B E | B |
| B's right, then left | E, then D | E, then D | E, then D |
Algorithm for Postorder + Inorder
BUILD_POST_IN(inLeft, inRight):
IF inLeft > inRight: RETURN NULL
rootValue = postorder[postIndex]
postIndex = postIndex - 1
root = new Node(rootValue)
split = position of rootValue in inorder
root.right = BUILD_POST_IN(split + 1, inRight)
root.left = BUILD_POST_IN(inLeft, split - 1)
RETURN root
How to Verify the Constructed Binary Tree Is Correct
A drawing is not complete until we check it. Traverse the constructed tree again and compare its outputs with the sequences in the question.
| Traversal | Output from the Tree | Check |
|---|---|---|
| Preorder | A B D E C F G | Matches input |
| Inorder | D B E A F C G | Matches input |
| Postorder | D E B F G C A | Matches expected output |
When both supplied sequences match, the reconstruction is valid. With distinct values, the Preorder + Inorder or Postorder + Inorder pair also guarantees uniqueness.
Can We Construct a Unique Binary Tree from Any Two Traversals?
No. It depends on which pair of traversals is given and whether labels are distinct. This difference is very important in university exams and technical interviews.
| Given Traversals | Unique Tree? | Reason |
|---|---|---|
| Preorder + Inorder | Yes, with distinct values | Preorder locates roots; Inorder splits children |
| Postorder + Inorder | Yes, with distinct values | Postorder locates roots; Inorder splits children |
| Preorder + Postorder | Not in general | One-child nodes can be left or right |
| Inorder alone | No | Root and structure are not identified |
| Preorder alone | No | Left/right shape remains unknown |
Why Preorder + Postorder Is Not Enough for a General Tree
Consider these two different Binary Trees. Both contain A and B, but B is on a different side.
A / B
A
\
B
Both trees have Preorder: A B and Postorder: B A. Therefore those two sequences do not reveal whether B belongs on the left or right.
What If Duplicate Values Are Present?
The simple root-search approach assumes unique values. With duplicates, a root value may appear at more than one position in Inorder, creating multiple possible splits. Extra information or a specific duplicate convention may be necessary.
Construct a Binary Tree from Numeric Traversals
Let us solve a second example using numbers. This helps you apply the same method to questions that do not use A, B, C labels.
Preorder: 10, 5, 3, 7, 20, 15, 30
Inorder: 3, 5, 7, 10, 15, 20, 30
Postorder (to verify): 3, 7, 5, 15, 30, 20, 10
- First Preorder value 10 becomes the root.
- In Inorder, the left side of 10 is 3, 5, 7; the right side is 15, 20, 30.
- Preorder's left portion begins with 5, so 5 is the left child of 10. Its children are 3 and 7.
- Preorder's right portion begins with 20, so 20 is the right child of 10. Its children are 15 and 30.
10
/ \
5 20
/ \ / \
3 7 15 30
Notice that these numbers also happen to satisfy the Binary Search Tree ordering rule, but reconstruction does not require a BST. This chapter works for ordinary Binary Trees with distinct labels, even if their values are not sorted.
Build Your Own Binary Tree from Preorder and Inorder
Enter two traversal sequences using commas or spaces. The builder will reconstruct a tree, show a node diagram and calculate Postorder to help you check your answer.
Live Tree Reconstruction Builder
Use distinct short labels (A, B, C or 10, 20, 30). Both inputs must contain the same labels. Maximum 12 nodes for a readable learning diagram.
A
/ \
B C
/ \ / \
D E F G
C Program to Construct Binary Tree from Preorder, Inorder and Postorder
This complete C program builds a tree in two independent ways: first from Preorder + Inorder, and then from Postorder + Inorder. Finally, it prints all three traversals of each tree so we can verify the reconstruction.
Node labels are distinct characters. The algorithm searches the Inorder portion to find the root position. It handles missing subtrees using NULL and releases dynamically allocated memory.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node {
char data;
struct Node *left;
struct Node *right;
} Node;
Node *createNode(char value) {
Node *p = malloc(sizeof *p);
if (p == NULL) {
fprintf(stderr, "Memory allocation failed\n");
exit(EXIT_FAILURE);
}
p->data = value;
p->left = NULL;
p->right = NULL;
return p;
}
int findInorder(
const char *in, int lo, int hi, char key
) {
for (int i = lo; i <= hi; ++i) {
if (in[i] == key) return i;
}
fprintf(stderr, "Invalid traversal pair\n");
exit(EXIT_FAILURE);
}
/* Preorder: root first; build left then right */
Node *buildPreIn(
const char *pre,
const char *in,
int lo,
int hi,
int *preIndex
) {
if (lo > hi) return NULL;
char value = pre[(*preIndex)++];
int split = findInorder(in, lo, hi, value);
Node *root = createNode(value);
root->left = buildPreIn(
pre, in, lo, split - 1, preIndex
);
root->right = buildPreIn(
pre, in, split + 1, hi, preIndex
);
return root;
}
/* Postorder backwards: root, right, left */
Node *buildPostIn(
const char *post,
const char *in,
int lo,
int hi,
int *postIndex
) {
if (lo > hi) return NULL;
char value = post[(*postIndex)--];
int split = findInorder(in, lo, hi, value);
Node *root = createNode(value);
root->right = buildPostIn(
post, in, split + 1, hi, postIndex
);
root->left = buildPostIn(
post, in, lo, split - 1, postIndex
);
return root;
}
void preorder(const Node *root) {
if (!root) return;
printf("%c ", root->data);
preorder(root->left);
preorder(root->right);
}
void inorder(const Node *root) {
if (!root) return;
inorder(root->left);
printf("%c ", root->data);
inorder(root->right);
}
void postorder(const Node *root) {
if (!root) return;
postorder(root->left);
postorder(root->right);
printf("%c ", root->data);
}
void freeTree(Node *root) {
if (!root) return;
freeTree(root->left);
freeTree(root->right);
free(root);
}
int main(void) {
const char pre[] = "ABDECFG";
const char in[] = "DBEAFCG";
const char post[] = "DEBFGCA";
int n = (int)strlen(in);
int preIndex = 0;
int postIndex = n - 1;
Node *first = buildPreIn(
pre, in, 0, n - 1, &preIndex
);
Node *second = buildPostIn(
post, in, 0, n - 1, &postIndex
);
printf("From Preorder + Inorder:\n");
printf("Preorder: ");
preorder(first);
printf("\n");
printf("Inorder: ");
inorder(first);
printf("\n");
printf("Postorder: ");
postorder(first);
printf("\n");
printf("From Postorder + Inorder:\n");
printf("Preorder: ");
preorder(second);
printf("\n");
printf("Inorder: ");
inorder(second);
printf("\n");
printf("Postorder: ");
postorder(second);
printf("\n");
freeTree(first);
freeTree(second);
return 0;
}
Expected Output
From Preorder + Inorder: Preorder: A B D E C F G Inorder: D B E A F C G Postorder: D E B F G C A From Postorder + Inorder: Preorder: A B D E C F G Inorder: D B E A F C G Postorder: D E B F G C A
Explanation of the C Program
- Node structure: Stores one character and pointers to left/right children.
- findInorder(): Finds the current root inside a given Inorder segment. If the root is not in that segment, the pair is invalid.
- buildPreIn(): Reads Preorder from the beginning; recursively creates left then right subtrees.
- buildPostIn(): Reads Postorder from the end; recursively creates right then left subtrees.
- Traversal functions: Print all three visiting orders so the reconstructed tree can be checked.
- freeTree(): Releases the allocated nodes from both trees.
Run This Code on Windows
Save as construct_tree_ch67.c.
Open PowerShell in the same folder and
run these commands if GCC is installed:
gcc -std=c11 -Wall -Wextra -pedantic construct_tree_ch67.c -o construct_tree_ch67 .\construct_tree_ch67.exe
Time and Space Complexity of Constructing a Binary Tree
In the C program above, the algorithm searches the current Inorder segment using a loop. A skewed tree may cause repeated scans of long sections. That can take O(n²) time in the worst case.
| Approach | Time | Extra Space |
|---|---|---|
| Linear search of Inorder (C code above) | O(n²) worst case | O(h + 1) recursion, excluding tree nodes |
| Index lookup with a hash map | O(n) expected | O(n) map + recursion stack |
| Memory for constructed tree | Not a time measure | O(n) for n allocated nodes |
Here n is the number of tree nodes and h is the tree height in edges. A balanced tree uses O(log n) recursion depth; a skewed tree can use O(n).
How can we improve the algorithm? Before recursion, store every Inorder value and its index in a hash map. Then the split position is found in expected O(1) time rather than scanning, and all n nodes can be built in expected O(n) total time.
Common Mistakes When Constructing Binary Trees from Traversals
- Using the first Postorder value as the root: Postorder's root is at the end, not the beginning.
- Forgetting Inorder boundaries: Values on one side of the root cannot be moved to the other subtree.
- Constructing left first while reading Postorder backwards: Build the right subtree first.
- Taking an incorrect number of Preorder elements: The size of the left Inorder portion tells us exactly how many nodes are on the left.
- Assuming Preorder + Postorder is always unique: A node with one child creates left/right ambiguity.
- Ignoring duplicate values: A value appearing multiple times can produce different possible tree shapes.
- Not checking the final traversal outputs: Recalculate them and compare with the given sequences.
FAQs on Constructing Binary Tree from Traversals
1. How do we construct a Binary Tree from Preorder and Inorder?
Select the first Preorder value as root, split Inorder around it, then recursively reconstruct the left and right subtrees using the corresponding Preorder portions.
2. How do we construct a Binary Tree from Postorder and Inorder?
Select the last Postorder value as root, split Inorder around it, then read Postorder backwards while constructing the right subtree first and the left subtree second.
3. Can we construct a unique Binary Tree using only Preorder and Postorder?
Not in general. A node with one child may be placed on the left or right while keeping the same Preorder and Postorder sequences.
4. Which traversal tells us where to split the left and right subtrees?
Inorder Traversal. The root's position separates left-subtree values from right-subtree values.
5. Can duplicate node values create ambiguity?
Yes. Distinct labels are assumed by the standard unique-reconstruction method. Duplicates may need extra information.
6. What is the time complexity of Binary Tree reconstruction?
Linear Inorder searching takes O(n²) worst-case time. Using an Inorder index hash map can reduce expected construction time to O(n).
7. Is the reconstructed tree always a Binary Search Tree?
No. It is a general Binary Tree unless the node values also satisfy the BST ordering rule.
Construct Binary Tree from Traversals: Quick Revision
- Preorder: first element is the root; build left, then right.
- Postorder: last element is the root; while reading backwards, build right, then left.
- Inorder: elements before root belong left; elements after root belong right.
- Unique: Preorder + Inorder, or Postorder + Inorder, with distinct values.
- Not generally unique: Preorder + Postorder.
- Verify: Run traversals of the constructed tree and compare with inputs.
- Time: O(n²) worst case with linear root searches; O(n) expected with indexed lookup.
- Example Preorder: A B D E C F G.
- Example Inorder: D B E A F C G.
- Example Postorder: D E B F G C A.
