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,

1. DFS based traversals:
   1. Inorder traversal
   2. Preorder traversal
   3. Postorder traversal
2. BFS based traversal:
   1. 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.

1. 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.
2. 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.
3. 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.

1. 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.
2. Level-order & preorder:
   We can't construct a unique binary tree from its level-order & preorder traversals.
   Say the preorder traversal is [1, 2]
   Level-order 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.
3. Level-order & postorder:
   We can't construct a unique binary tree from its level-order & postorder traversals.
   Say the postorder traversal is [2, 1]
   Level-order 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.