Home »
Data Structure
Given which two traversals you can determine the tree uniquely?
In this article, we are going to describe given which two traversal, we can construct the binary tree uniquely.
Submitted by Radib Kar, on August 03, 2020
Prerequisite: Inorder traversal, Preorder traversal, Postorder traversal, Level order traversal
We have read already about various tree traversals. To categorize them,

DFS based traversals:
 Inorder traversal
 Preorder traversal
 Postorder traversal

BFS based traversal:
 Level order traversal
Now the thing is given a traversal can we uniquely determine the binary tree?
For example,
The traversals for the below tree is:
1
/ \
2 3
/ /
4 5
Preorder: [1, 2, 4, 3, 5]
Inorder: [4, 2, 1, 5, 3]
Postorder: [4, 2, 5, 3, 1]
Level order: [1, 2, 3, 4, 5]
Now, say we had only one traversal, for example preorder:
Will you be able to construct a tree uniquely?
From a preorder traversal we have only information about root, but we don’t know up to which part is its left subtree and which is right subtree. Actually we can construct Catalan(n) number of trees from its preorder traversal where Catalan(n) is nth Catalan number
Same goes for inorder, postorder traversal too. So, it’s confirmed that we can’t convert to a unique binary tree from only one traversal. So we need at least two. But is it possible for any two condition?
The thing is if we are given inorder traversal and any one of other traversal then we can construct unique binary tee from these two traversals.
 Inorder & preorder:
We can construct a unique binary tree from its preorder & inorder traversals. Follow the article to see how to construct a unique binary tree from its inorder & preorder traversal.
 Inorder & preorder:
We can construct a unique binary tree from its postorder & inorder traversals. Follow the article to see how to construct a unique binary tree from its inorder & postorder traversal.
 Inorder & level order:
We can construct a unique binary tree from its level order & inorder traversals. Follow the article to see how to construct a unique binary tree from its inorder & level order traversal.

Postorder & preorder:
We can't construct a unique binary tree from its preorder & postorder traversals.
Say the preorder traversal is [1, 2]
postorder traversal is [2, 1]
then we can have any of the trees
1 OR 1
\ /
2 2
So, we can't construct the tree uniquely.

Levelorder & preorder:
We can't construct a unique binary tree from its levelorder & preorder traversals.
Say the preorder traversal is [1, 2]
Levelorder traversal is [1, 2]
then we can have any of the trees
1 OR 1
\ /
2 2
So, we can't construct the tree uniquely.

Levelorder & postorder:
We can't construct a unique binary tree from its levelorder & postorder traversals.
Say the postorder traversal is [2, 1]
Levelorder traversal is [1, 2]
then we can have any of the trees
1 OR 1
\ /
2 2
So, we can't construct the tree uniquely.
So, we require inorder traversal and one another traversal to construct the tree uniquely.
TOP Interview Coding Problems/Challenges