Traversal reconstruction questions reward a fixed procedure, not a lucky sketch. Find the root, split the inorder sequence, and recurse on the two pieces. If you preserve the segment boundaries, left and right subtrees cannot get mixed.
The first decision is equally important: does the given traversal pair determine a unique tree at all?
Which traversal pairs determine a unique binary tree?
Assume all node labels are distinct. A general binary tree is uniquely determined by these pairs:
Given traversals | Unique general binary tree? | Reason |
|---|---|---|
Inorder + preorder | Yes | Preorder gives each root; inorder splits left and right |
Inorder + postorder | Yes | Postorder gives each root; inorder splits left and right |
Inorder + level order | Yes | Earliest level-order node in each inorder segment is its root |
Preorder + postorder | No, in general | A single child may be left or right |
Preorder + postorder for a full tree | Yes | Every internal node has two children, removing the single-child ambiguity |
Inorder is the indispensable traversal in the first three pairs because it places the entire left subtree before the root and the entire right subtree after it. Preorder identifies a root before its descendants. Postorder identifies it after its descendants. Together with the inorder split, either supplies all the recursive boundaries.
Why do preorder and postorder fail for a general tree? Preorder A, B and postorder B, A describe both a tree where B is A's left child and one where B is A's right child. Neither traversal records the missing side.
For a wider revision of terminology and properties, see binary trees and binary search trees.
Worked reconstruction from preorder and inorder
Given:
Preorder: D, B, A, C, F, E, G
Inorder: A, B, C, D, E, F, GThere are seven distinct nodes. Rebuild the tree step by step.
Step 1: choose the overall root. The first preorder element is D, so D is the root. In inorder, everything left of D belongs to the left subtree and everything right belongs to the right subtree:
Left inorder: A, B, C
Root: D
Right inorder: E, F, GThe left segment has three nodes, so the next three preorder elements form the left subtree's preorder. The remaining three form the right subtree's preorder:
Left preorder: B, A, C
Right preorder: F, E, GStep 2: build the left subtree. Its first preorder element is B. Splitting left inorder A, B, C around B gives A on the left and C on the right. Therefore A is B's left child and C is B's right child.
Step 3: build the right subtree. Its first preorder element is F. Splitting right inorder E, F, G around F gives E on the left and G on the right. Therefore E is F's left child and G is F's right child.
The final tree is:
D
/ \
B F
/ \ / \
A C E G
Verify the result twice. Its preorder is root, left, right: D, B, A, C, F, E, G. Its inorder is left, root, right: A, B, C, D, E, F, G. Both exactly match the input.
An implementation can use an inorder index map so each root position is found in constant time. With careful segment indices, the full reconstruction then takes linear time. In a hand-solved question, writing the paired segments gives the same protection against boundary mistakes.
The BST shortcut: preorder alone can be enough
A binary search tree adds an ordering rule: every key in the left subtree is smaller than the root, and every key in the right subtree is larger. For distinct keys, its inorder traversal is therefore the sorted key sequence. That means preorder alone determines the BST.
Take this preorder:
40, 30, 20, 35, 60, 50, 70Start with root 40. Values below 40, 30, 20, 35, form the left-subtree segment. Values above 40, 60, 50, 70, form the right-subtree segment. In the left segment, 30 is the root, with 20 below it and 35 above it. In the right segment, 60 is the root, with 50 below it and 70 above it.
The result has 40 at the root; children 30 and 60; and leaves 20, 35, 50, and 70. Its sorted inorder is 20, 30, 35, 40, 50, 60, 70, confirming the BST property.
The shortcut depends on the BST ordering rule. Preorder alone does not uniquely identify an unrestricted binary tree. Practise that distinction with the tree-focused data structures questions.
Counting trees when only one traversal is given
If a fixed preorder, postorder, or inorder sequence of n distinct labels is the only information, the number of possible binary-tree structures is the nth Catalan number:
C_n = (1 / (n + 1)) x binomial(2n, n)For n = 3:
C_3 = (1 / 4) x binomial(6, 3)
= (1 / 4) x 20
= 5So one traversal of three distinct nodes is consistent with five binary-tree structures. The labels occupy each structure in the order required by the given traversal. Do not confuse this with the number of BSTs on three distinct keys, although that count is also Catalan for a different reason.
How GATE tests traversal reconstruction
Questions may ask for the root of a subtree, a node's parent, the resulting postorder, or the number of possible trees. The most common traps are assuming preorder plus postorder is always unique, consuming the wrong number of preorder items for a subtree, and applying the BST shortcut to an ordinary binary tree.
Duplicate labels need extra information because locating a root value in inorder may no longer give a unique split. Unless a question defines duplicate handling, the standard reconstruction result assumes distinct labels.
Confirm current syllabus and paper instructions on the official GATE portal of the organising IIT. Use the GATE CS preparation category to place tree reconstruction within the larger preparation plan.
The short version
Use preorder or postorder to select a root, use inorder to divide left from right, and recurse with matching segment sizes. Preorder plus postorder is not enough for a general tree, but it works for a full tree. For a BST with distinct keys, preorder alone works because inorder is sorted.
After rebuilding the worked tree without looking, use the GATE Test Series for timed traversal and counting questions. Verify every answer by generating the traversals from your final tree.
