Self-checkedTier 1 18 min readpds.tree-construction-from-traversals

Constructing a tree from its traversals

Which pairs of traversals determine a binary tree (inorder with preorder, postorder or level order do; preorder with postorder does not, unless the tree is full), the recursive algorithm that rebuilds the tree, and the counting questions that follow (how many trees share a preorder, how many share a preorder and a postorder).

Why it exists

A traversal turns a tree into a list, and information is lost on the way. The question is how much: which lists, taken together, still pin down the tree? The answer is a favourite GATE topic: given two of the traversals, draw the tree or write the third. It also leads to counting questions. This page gives the rule (all trees in this page have distinct keys), the algorithm, and the cases that do not work.

Prerequisites

Binary tree traversals

Precise definitions

Throughout, the keys in the tree are all different. (With repeated keys the lists no longer identify nodes, so the uniqueness statements below no longer follow.)

Which pairs of traversals determine the tree

Given	Tree unique?	Why
Inorder and preorder	yes	the first preorder item is the root; the inorder list splits at the root
Inorder and postorder	yes	the last postorder item is the root; the inorder list splits at the root
Inorder and level order	yes	the first level-order item is the root, and the same split works
Preorder and postorder	not in general	they cannot say whether a lone child is a left or a right child
Preorder and postorder of a full binary tree	yes	every node has 0 or 2 children, so no choice is hidden
One traversal only	no	many shapes share it (but see BSTs below)

Inorder is what separates the left subtree from the right subtree. The other list (preorder, postorder or level order) supplies the root of each subtree.

Binary search trees are a special case. The inorder of a BST is the keys in sorted order, so one traversal (preorder or postorder, with the keys) determines the BST, because the sorted keys can be written down and used as the inorder list.

The algorithm from inorder and preorder

The first item of the preorder range is the root.
Find that root in the inorder range, at position $k$ . Everything to the left of $k$ in the inorder range is the left subtree, everything to the right is the right subtree.
The left subtree has $k - lo$ nodes, so the next $k - lo$ items of preorder are the left subtree's preorder, and the remaining items are the right subtree's.
Repeat for both subtrees.

From inorder and postorder use the last item of the postorder range as the root; when processing the postorder from the end, handle the right subtree before the left one (postorder is left, right, root, so read backwards it is root, right, left).

Cost. With a linear search for the root in step 2 the worst case is $\Theta(n^2)$ (for example a left-leaning chain, whose preorder is the keys in decreasing order; a right chain costs only $n$ comparisons). If the position of every key in the inorder list is stored once in a table, step 2 takes constant time and the whole construction is $\Theta(n)$ . This needs keys that can index an array (such as $1..n$ ), or a hash table (expected $\Theta(n)$ ); with sorting instead it is $O(n \log n)$ . The recursion depth is $\Theta(n)$ on a chain.

Why preorder and postorder are not enough

Take two nodes, 1 as the root and 2 as its only child. If 2 is the left child, preorder is 1 2, postorder 2 1, inorder 2 1. If 2 is the right child, preorder is 1 2, postorder 2 1 again, but inorder is 1 2. The two trees have the same preorder and the same postorder and are different trees: preorder and postorder cannot tell on which side a lone child hangs. Every node with exactly one child hides one such binary choice.

Count. If the tree has $k$ nodes with exactly one child, there are exactly $2^k$ binary trees with that preorder and postorder. A full binary tree has $k = 0$ , so it is the only one.

Counting facts that follow

A fixed preorder of $n$ distinct keys is shared by exactly $C_n = \frac{1}{n+1}\binom{2n}{n}$ different binary trees (the Catalan number: 1, 2, 5, 14, 42, ...). The same is true for a fixed inorder or a fixed postorder.
The inorder sequences of those $C_n$ trees (with the preorder $1, 2, \ldots, n$ ) are exactly the $C_n$ orders in which a stack can output $1, \ldots, n$ pushed in order. This is the reason the two Catalan counts agree.
If preorder equals inorder, no node has a left child (the tree is a right chain). If postorder equals inorder, no node has a right child. If preorder is the reverse of postorder, every node has at most one child, so the tree is a chain whose turns (left or right) are free: $2^{n-1}$ trees.

How it works

The animation runs the exact build() function shown, with preorder 1 2 4 5 7 3 6 and inorder 4 2 7 5 1 3 6. Watch three things. First, each call creates a node for the next preorder item and finds it in the inorder range, which fixes the sizes of its two subtrees. Second, a node is not linked to its parent until the recursive call that built it returns, so for a while the picture shows several separate pieces. Third, the blue list is the chain of calls in progress, which is a path from the root down.

Building a tree from its preorder and inorder lists

Real run

C source

1#include <stdlib.h>

3struct node {

4 int data;

5 struct node *left, *right;

6};

8static int p;

10struct node *build(const int *pre, const int *in, int lo, int hi) {

11 if (lo > hi)

12 return NULL;

13 struct node *t = calloc(1, sizeof *t);

14 t->data = pre[p++];

15 int k = lo;

16 while (in[k] != t->data)

17 k++;

18 t->left = build(pre, in, lo, k - 1);

19 t->right = build(pre, in, k + 1, hi);

20 return t;

21}

Tree (read from the program's real pointers)

build() calls in progress (the node created by each)

Blue ring = on the call stack (or the search path), amber ring = waiting in the queue, green with a number = already printed (and in which order). The filled node is the one this step is about.

Step 1

preorder gives the next root: 1. A new node is created for the inorder range 0..6.

1 / 36

Preorder 1 2 4 5 7 3 6 and inorder 4 2 7 5 1 3 6 are passed to build() by hidden driver code. The function shown is the exact code that runs. A node appears as soon as it is created but is linked to its parent only when the recursive call that built it returns. Produced by: real execution: the tree, the call stack, the queue and the printed output are read from the running program at each step. gcc (Debian 14.2.0-19) 14.2.0. gcc -O0 -o prog prog.c && setarch x86_64 -R ./prog

Worked examples

EX 1Preorder and inorder to a tree, printed as postorder

Easy

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *left, *right;
};
 
static int p;
 
static struct node *build(const int *pre, const int *in, int lo, int hi) {
    if (lo > hi) return NULL;
    struct node *t = calloc(1, sizeof *t);
    if (t == NULL) exit(1);
    t->data = pre[p++];
    int k = lo;
    while (in[k] != t->data) k++;
    t->left = build(pre, in, lo, k - 1);
    t->right = build(pre, in, k + 1, hi);
    return t;
}
 
static void post(const struct node *t) {
    if (t == NULL) return;
    post(t->left);
    post(t->right);
    printf("%d ", t->data);
}
 
int main(void) {
    int pre[7] = {1, 2, 4, 5, 7, 3, 6};
    int in[7] = {4, 2, 7, 5, 1, 3, 6};
    post(build(pre, in, 0, 6));
    printf("\n");
    return 0;
}

Output:

4 7 5 2 6 3 1

By hand. Root 1; in the inorder list 4 2 7 5 | 1 | 3 6, so the left subtree has 4 nodes and the right 2. The next 4 preorder items 2 4 5 7 are the left subtree, 3 6 the right. Left subtree: root 2, inorder 4 | 2 | 7 5, so 4 on the left and 7 5 on the right (preorder 5 7: root 5, and 7 sits left of 5 in the inorder list, so 7 is 5's left child). Right subtree: root 3, inorder 3 | 6, so 6 is 3's right child. The postorder of that tree is 4 7 5 2 6 3 1.

EX 2Inorder and postorder to a tree, printed as preorder

Medium

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *left, *right;
};
 
static int q;
 
static struct node *build(const int *in, const int *post, int lo, int hi) {
    if (lo > hi) return NULL;
    struct node *t = calloc(1, sizeof *t);
    if (t == NULL) exit(1);
    t->data = post[q--];
    int k = lo;
    while (in[k] != t->data) k++;
    t->right = build(in, post, k + 1, hi);
    t->left = build(in, post, lo, k - 1);
    return t;
}
 
static void pre(const struct node *t) {
    if (t == NULL) return;
    printf("%d ", t->data);
    pre(t->left);
    pre(t->right);
}
 
int main(void) {
    int in[7] = {4, 2, 7, 5, 1, 3, 6};
    int post[7] = {4, 7, 5, 2, 6, 3, 1};
    q = 6;
    pre(build(in, post, 0, 6));
    printf("\n");
    return 0;
}

Output:

1 2 4 5 7 3 6

Reading it. The postorder list is consumed from the end, and the right subtree is built before the left: read backwards, postorder is root, right, left. If the two build calls were swapped, the tree would come out wrong. The result is the original tree (preorder 1 2 4 5 7 3 6).

EX 3Two different trees with the same preorder and the same postorder

GATE level

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *left, *right;
};
 
static struct node *mk(int d, struct node *l, struct node *r) {
    struct node *t = malloc(sizeof *t);
    if (t == NULL) exit(1);
    t->data = d;
    t->left = l;
    t->right = r;
    return t;
}
 
static void pre(const struct node *t) {
    if (t == NULL) return;
    printf("%d ", t->data);
    pre(t->left);
    pre(t->right);
}
 
static void in(const struct node *t) {
    if (t == NULL) return;
    in(t->left);
    printf("%d ", t->data);
    in(t->right);
}
 
static void post(const struct node *t) {
    if (t == NULL) return;
    post(t->left);
    post(t->right);
    printf("%d ", t->data);
}
 
static void show(const char *name, const struct node *t) {
    printf("%s: ", name);
    pre(t);
    printf("/ ");
    post(t);
    printf("/ ");
    in(t);
    printf("\n");
}
 
int main(void) {
    show("A", mk(1, mk(2, NULL, NULL), NULL));
    show("B", mk(1, NULL, mk(2, NULL, NULL)));
    return 0;
}

Output (preorder / postorder / inorder):

A: 1 2 / 2 1 / 2 1
B: 1 2 / 2 1 / 1 2

Reading it. Tree A has 2 as the left child of 1, tree B has 2 as the right child. Their preorders are equal, their postorders are equal, and only the inorder lists tell them apart. With one node that has a single child, there are $2^1 = 2$ trees for this pair of lists. A tree with $k$ single-child nodes has $2^k$ .

EX 4A full binary tree is determined by preorder and postorder

GATE level

#include <stdio.h>
#include <stdlib.h>
 
#define N 7
 
struct node {
    int data;
    struct node *left, *right;
};
 
static int pi;
 
static struct node *build(const int *pre, const int *post, int lo, int hi) {
    if (pi >= N || lo > hi) return NULL;
    struct node *t = calloc(1, sizeof *t);
    if (t == NULL) exit(1);
    t->data = pre[pi++];
    if (lo == hi || pi >= N) return t;
    int k = lo;
    while (post[k] != pre[pi]) k++;
    t->left = build(pre, post, lo, k);
    t->right = build(pre, post, k + 1, hi - 1);
    return t;
}
 
static void in(const struct node *t) {
    if (t == NULL) return;
    in(t->left);
    printf("%d ", t->data);
    in(t->right);
}
 
int main(void) {
    int pre[N] = {1, 2, 4, 5, 3, 6, 7};
    int post[N] = {4, 5, 2, 6, 7, 3, 1};
    in(build(pre, post, 0, N - 1));
    printf("\n");
    return 0;
}

Output:

4 2 5 1 6 3 7

Reading it. The tree is full: every node has 0 or 2 children. The root is the first preorder item (1). The second preorder item (2) must be the root of the left subtree, because with two children the left one comes right after its parent. Find 2 in the postorder list: everything up to and including it is the left subtree (4 5 2), the rest except the last item (the root) is the right subtree (6 7 3). Repeat. The function is correct only for full trees: for a node with one child it would wrongly make that child a left child.

EX 5Letters: from preorder and inorder to postorder

GATE level

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
struct node {
    char data;
    struct node *left, *right;
};
 
static int p;
 
static struct node *build(const char *pre, const char *in, int lo, int hi) {
    if (lo > hi) return NULL;
    struct node *t = calloc(1, sizeof *t);
    if (t == NULL) exit(1);
    t->data = pre[p++];
    int k = lo;
    while (in[k] != t->data) k++;
    t->left = build(pre, in, lo, k - 1);
    t->right = build(pre, in, k + 1, hi);
    return t;
}
 
static void post(const struct node *t) {
    if (t == NULL) return;
    post(t->left);
    post(t->right);
    putchar(t->data);
}
 
int main(void) {
    const char *pre = "ABDECF";
    const char *in = "DBEAFC";
    post(build(pre, in, 0, (int)strlen(in) - 1));
    printf("\n");
    return 0;
}

Output:

DEBFCA

By hand. Preorder A B D E C F, inorder D B E A F C. Root A. Inorder splits as D B E | A | F C. Left subtree has 3 nodes, preorder B D E: root B, inorder D | B | E, so D is its left child and E its right. Right subtree preorder C F: root C, inorder F | C, so F is the left child of C. Postorder: D E B, then F C, then A.

EX 6Counting the trees that share a preorder

GATE level

#include <stdio.h>
#include <string.h>
 
#define MAXC 42
 
static int S[6][MAXC][5];
static int C[6];
 
static void gen(int m) {
    if (m == 0) {
        C[0] = 1;
        return;
    }
    C[m] = 0;
    for (int k = 0; k < m; k++)
        for (int a = 0; a < C[k]; a++)
            for (int b = 0; b < C[m - 1 - k]; b++) {
                int *s = S[m][C[m]++];
                int n = 0;
                for (int i = 0; i < k; i++) s[n++] = S[k][a][i] + 1;
                s[n++] = 0;
                for (int i = 0; i < m - 1 - k; i++) s[n++] = S[m - 1 - k][b][i] + k + 1;
            }
}
 
static int valid(const int *p, int n) {
    int st[8], top = -1, next = 0;
    for (int i = 0; i < n; i++) {
        while (top < 0 || st[top] != p[i]) {
            if (next >= n) return 0;
            st[++top] = next++;
        }
        top--;
    }
    return 1;
}
 
static int distinct(int m) {
    int d = 0;
    for (int i = 0; i < C[m]; i++) {
        int dup = 0;
        for (int j = 0; j < i; j++)
            if (memcmp(S[m][i], S[m][j], (size_t)m * sizeof(int)) == 0) dup = 1;
        d += !dup;
    }
    return d;
}
 
static int all_valid(int m) {
    int v = 0;
    for (int i = 0; i < C[m]; i++) v += valid(S[m][i], m);
    return v;
}
 
int main(void) {
    for (int m = 0; m <= 5; m++) gen(m);
    printf("%d %d %d %d %d %d\n", C[4], distinct(4), all_valid(4), C[5], distinct(5), all_valid(5));
    return 0;
}

Output:

14 14 14 42 42 42

Reading it. The program builds every binary tree whose preorder is $0, 1, \ldots, m - 1$ by choosing how many nodes $k$ go into the left subtree (the root is first in preorder, then $k$ left-subtree nodes, then the rest on the right), and records the inorder sequence of each. For 4 nodes there are 14 trees and 14 different inorder sequences, all of which a stack can produce; for 5 nodes, 42 of each. So "how many binary trees have preorder $1, 2, 3, 4$ ?" is 14, and the same number counts the possible inorders, which are exactly the stack-permutations of the stack page.

Cheat box

Distinct keys. Inorder + (preorder or postorder or level order) determines the tree. Preorder + postorder does not, except for a full binary tree.
Preorder: root is the first. Postorder: root is the last. Find it in inorder: left of it is the left subtree, right of it the right subtree.
Left subtree size $= k - lo$ (index of root in inorder minus start). Split the other list by sizes (preorder and postorder). For level order, filter the list instead: keep the keys that lie in the left inorder range, then those in the right range, each in their original order.
From postorder, build from the end, right subtree first.
Same preorder and postorder: $2^k$ trees, $k$ = number of nodes with exactly one child.
Same preorder (distinct keys): $C_n$ trees. Same for inorder or postorder alone.
Preorder $=$ inorder: no left children. Postorder $=$ inorder: no right children. Preorder $=$ reversed postorder: a chain, $2^{n-1}$ shapes.
BST: a preorder, a postorder or a level order alone is enough (sort the keys to get the inorder). Inorder alone is never enough.
With a lookup table for inorder positions the construction is $\Theta(n)$ ; otherwise $\Theta(n^2)$ worst case.

Traps and GATE patterns

Connections

Builds on

Binary tree traversals

Unlocks

Binary tree traversalsuses Counting binary treesuses Binary search treesuses

Across subjects

No cross-subject links yet.

Within this subject

Counting binary treesuses Binary search treesuses Stack (abstract data type)analogous-to Recursion patternsuses

The first step is the traversal definitions in reverse. The Catalan count of shapes is developed on the counting page, and its link to stack-obtainable permutations is the one checked for $n = 4$ and $5$ in example 6 and discussed on the stack page. For a binary search tree the sorted keys supply the missing inorder list, so a preorder alone is enough. The algorithm is a divide-and-conquer recursion (recursion patterns).

PYQs

6 previous year questions from your book. I re-solved each one myself (6 by running or simulating, 0 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2026 · Set 1Q2 · page 66 of the book

The following sequence corresponds to the
preorder traversal of a binary search tree
T: 50, 25, 13, 40, 30, 47, 75, 60, 70, 80, 77 .
The position of the element 60 in the post-order
traversal of T is
.

GATE 2020 · MCQQ13 · page 68 of the book

The preorder traversal of a binary search tree is 15,
10, 12, 11, 20, 18, 16, 19.
Which one of the following is the postorder
traversal of the tree?

(a)20, 19, 18, 16, 15, 12, 11, 10
(b)11, 12, 10, 16, 19, 18, 20, 15
(c)10, 11, 12, 15, 16, 18, 19, 20
(d)19, 16, 18, 20, 11, 12, 10, 15

GATE 2017 · MCQ · 1 markQ15 · page 68 of the book

The pre-order traversal of a binary search tree is
given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20.
Then the post-order traversal of this tree is:

(a)2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20
(b)2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12
(c)7, 2, 6, 8, 9, 10, 20, 17, 19, 15, 16, 12
(d)7, 6, 2, 10, 9, 8, 15, 16, 17, 20, 19, 12

GATE 2013 · MCQQ32 · page 71 of the book

The preorder traversal sequence of a binary search
tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one
of the following is the postorder traversal sequence
of the same tree?

(a)10, 20, 15, 23, 25, 35, 42, 39, 30
(b)15, 10, 25, 23, 20, 42, 35, 39, 30
(c)15, 20, 10, 23, 25, 42, 35, 39, 30
(d)15, 10, 23, 25, 20, 35, 42, 39, 30 } the appropriate expression for the two boxes B1 and B2 are
(a)B1: (1+height(n→right)) B2: (1+max(h1,h2))
(b)B1: (height(n→right) B2: (1+max(h1,h2))
(c)B1: height(n→right) B2: max(h1,h2)
(d)B1: (1+ height(n→right)) B2: max(h1,h2)

GATE 2014 · Set 3 · MCQQ43 · page 73 of the book

The inorder and preorder traversal of a binary tree
are
Inorder: d b e a f c g
Preorder: a b d e c f g
The postorder traversal of the binary tree is:

(a)d e b f g c a
(b)e d b g f c a
(c)e d b f g c a
(d)d e f g b c a

GATE 2005Q49 · page 74 of the book

Postorder traversal of a given binary search tree, T
produces the following sequence of keys:
10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29

Which one of the following sequences of keys can
be the result of an in-order traversal of the tree T?

(a)9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95
(b)9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29
(c)29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95
(d)95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29

Self-check

Question 1

Preorder P Q R S T, postorder R S Q T P. Is the tree unique? What are the possible inorders?

Show answer

The tree is unique. The root is P. The next preorder item Q is the root of the first subtree, and in postorder Q ends the block R S Q, so one subtree of P is {Q, R, S} and the other is {T}. Both subtrees are non-empty, so there is no hidden left-or-right choice: the one that comes first in preorder (Q's) is the left subtree. Inside it, the same argument gives Q with left child R and right child S. Every node has 0 or 2 children, so the tree is full, which is why preorder and postorder suffice. The inorder is R Q S P T.

Question 2

Inorder 3 1 4 2 5 and level order 2 1 5 3 4. Draw the tree and give its preorder.

Show answer

Root is 2 (first in level order). Inorder: 3 1 4 | 2 | 5, so the left subtree has 3, 1, 4 and the right subtree is 5. Level order keeps the relative order within each side: for the left subtree 1 3 4, root 1 with inorder 3 | 1 | 4: left child 3, right child 4. Right subtree: just 5. Preorder: 2 1 3 4 5.

Question 3

How many different binary trees have preorder equal to 1 2 3?

Show answer

Preorder with distinct keys is shared by the Catalan number of trees, $C_3 = 5$ .

Question 4

A tree has 6 nodes, 2 of which have exactly one child. How many binary trees have the same preorder and the same postorder as it?

Show answer

Each single-child node can independently hang its child on the left or the right: $2^2 = 4$ trees (including the given one).

Question 5

The preorder and inorder of a binary tree with 5 distinct keys are the same list. What does the tree look like, and how many such trees exist for a given list?

Show answer

Preorder is root, left, right and inorder is left, root, right. They agree only if no node has a left subtree, so each node has only a right child: a right-leaning chain. For a given list there is exactly one such tree.

Revision card

One-screen revision

Distinct keys. Inorder + one of pre/post/level: unique. Pre + post: unique only for a full binary tree; otherwise $2^k$ trees ( $k$ = single-child nodes).
Root: first of preorder, last of postorder. Split inorder at it; split preorder/postorder by size (level order: filter by membership).
Postorder rebuild: from the end, right subtree first.
One preorder (or inorder, or postorder) of $n$ keys: $C_n$ trees. BST: preorder, postorder or level order alone suffices (never inorder alone).
Pre $=$ in: right chain. Post $=$ in: left chain. Pre $=$ reverse post: chain with free turns.
Naive $\Theta(n^2)$ , with an inorder position table $\Theta(n)$ .

References

·Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 3rd ed., Section 12.1 What is a binary search tree? (the tree walks themselves; the CLRS exercises there do not cover reconstruction from two walks, as far as can be told without the book, so the reconstruction itself is derived on this page)

Verification

The animation replays a real run of the shown build() function on real arrays: the nodes are read from the program's heap, and the test suite checks that the tree it builds has the same shape as the tree used by the traversal pages and that nodes appear before they are linked. All C programs on this page are compiled with -Wall -Wextra -Werror and run by npm run verify:c, also under AddressSanitizer and UBSan (leak detection off). The uniqueness and counting statements (inorder with preorder or postorder is unique; preorder and postorder together leave 2^k trees where k is the number of nodes with exactly one child; preorder equal to reversed postorder forces a chain; the inorder sequences of trees with preorder 1..n are exactly the stack-obtainable permutations) were checked by enumerating every tree shape up to 7 nodes in a one-off script that is not part of the repository; the counts for 4 and 5 nodes are also computed by a C program on this page. The textbook section number was written from memory and has NOT been checked against the book. The prose and the GATE-pattern claims have NOT yet had a human textbook check (the independent second pass is described at the end of these notes). SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and the numbers re-derived by hand (long C programs were not re-read line by line: they are compiled and compared by npm run verify:c, and their printed outputs were checked against the prose). No defect found. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

Binary tree traversals

Counting binary trees