3/25/25, 11:12 AM How to construct a Binary Tree using different traversals?

- Tutorial

Login

How to construct a Binary Tree using

different traversals?

Problem Statement: Requirements are needed to construct a unique binary tree. In this
article, we will understand the traversals required to construct a unique binary tree.

# Constructing A Unique Binary tree using a single traversal.

If we are given any traversal, be it postorder, preorder, or inorder; it is not possible to

For example:

For a preorder traversal: [ 1 2 3 4 5 ], all the following trees can be constructed.

https://takeuforward.org/binary-tree/how-to-construct-a-binary-tree-using-different-traversals/ 1/1
3/25/25, 11:13 AM How to construct a Binary Tree using different traversals? - Tutorial

Login

For an inorder traversal : [ 1 2 3 4 5 ], all the following trees can be constructed.

Conclusion: We cannot construct a unique binary tree with just one traversal.

https://takeuforward.org/binary-tree/how-to-construct-a-binary-tree-using-different-traversals/ 1/1
3/25/25, 11:14 AM How to construct a Binary Tree using different traversals? - Tutorial

Conclusion: We cannot construct a unique binary tree with just one traversal. Login

# Constructing A Unique Binary tree using two traversals.

Case 1: Using Preorder and Postorder Traversal

Given:

We see that the following different trees can be constructed using the above two traversals:

Conclusion: We cannot construct a unique binary tree using preorder and postorder
traversal.

https://takeuforward.org/binary-tree/how-to-construct-a-binary-tree-using-different-traversals/ 1/1
3/25/25, 11:15 AM How to construct a Binary Tree using different traversals? - Tutorial

Conclusion: We cannot construct a unique binary tree using preorder and postorder
Login
traversal.

Case 2: Using preorder and inorder traversal

Given:

We will try to construct a binary tree using the above two traversals.

Step 1:

We know that the first element of a preorder traversal (root, left, right) is the root of the tree
therefore, we can say that 3 is the root of the tree. We can then find 3 in the inorder
traversal and find the left subtree and right subtree of node 3 from it as inorder traversal is
(left, root, right).

Step 2:

As 9 is the only element to the left of 3 in inorder traversal, we can conclude that the left
subtree of node 3 contains a single node 9. Preorder traversal also contains node 9 as the
second element. Therefore the remaining nodes in the preorder traversal will be the right
subtree of node 3.

https://takeuforward.org/binary-tree/how-to-construct-a-binary-tree-using-different-traversals/ 1/1
3/25/25, 11:16 AM How to construct a Binary Tree using different traversals? - Tutorial
subtree of node 3 contains a single node 9. Preorder traversal also contains node 9 as the
Login
second element. Therefore the remaining nodes in the preorder traversal will be the right

Step 3:

Now, we will work on the right subtree of node 3. We know that is given by the last three
elements of preorder traversal. As discussed in step 1, the first node will give us the root of
the right subtree, then we can find that element (20) in the inorder traversal. Elements left
to element 20 will give us the left subtree and elements right to it will give the right subtree
of node 20.

Conclusion: We can construct a unique binary tree using inorder and preorder traversal.

Similarly, it can be shown that a unique binary tree can be constructed using inorder and
postorder traversal as in postorder traversal the root node is given as the last element.

The special feature of the inorder traversal is that it helps us to identify a node and its left

and right subtree. This is not provided by any other traversal therefore whenever we
are provided in order traversal with one other traversal, we can easily construct a unique binary tree.

1/1