Find a binary tree given only in-order traversal

Question

I'm given an in-order traversal and need to find a binary tree. I referred my sites and most of them said it is not possible. However, i think a non-unique binary tree is possible. Can i find a binary tree using just given in-order traversal? If not, can i find a corresponding pre-order traversal from the given in-order traversal?

I tried to convert the in-order into pre-order by selecting the central node of in-order as the root but I'm not sure if its correct. Please guide me.

Thank you.

Milo P · Accepted Answer · 2016-03-25 22:48:12Z

2

Given just the in-order traversal of the nodes, and no more information in the question, you can find a binary tree, but as you said, there won't be a unique solution (especially if the tree doesn't have to be balanced). As a result, you can again find a pre-order traversal.

As an example, if your in-order traversal is [1,2,3,4,5,6,7,8], then even if the tree is balanced, there are multiple possibilities for the root node (namely, 4 or 5). If the tree doesn't have to be balanced, you could potentially pick any of these as the root node.

Here's an example of a non-balanced tree you could build after arbitrarily choosing 4 as the root node:

      4
     /  \
    3    6
   /    / \
  2    5   7
 /          \
1            8

Pre-order traversal for this tree would yield 4,3,2,1,6,5,7,8. Again, if the only requirements are that you just find a binary tree, this is just as valid as setting 1 as the root node and making everything else a right node:

The pre-order traversal for this tree would be 1,2,3,4,5,6,7,8. Since these trees both generate the same in-order traversal, but different pre-order traversals, there isn't guaranteed to be a single, unique tree or even a single, unique pre-order traversal for a given in-order traversal.

edited Mar 25, 2016 at 22:48

answered Jan 22, 2016 at 19:14

Milo P

1,4722 gold badges35 silver badges45 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Nisarg Patel Over a year ago

So how do i find the binary tree with given in-order? Can you please explain me? Thanks.

WingedPanther73 Over a year ago

@Nisarg Patel Clarifying what Milo said above, there is nothing that stops you from having a "binary tree" that only uses left branches, or only uses right branches. Even in the case of a balanced binary tree, unless you have exactly 2^n-1 branches, you may have preferred left or right children for population. Given all that, the pre-order is not unique, because it is dependent on the arrangement of nodes within the tree. If you build a binary tree using whatever arrangement you prefer, you can then build the pre-order list based on that particular tree.

lrleon · Accepted Answer · 2016-01-22 20:32:54Z

0

For more of one node there is no a unique binary search tree that contains the inorder traversal.

But if you want a tree, then just perform a random shuffle of inorder sequence and then insert the resulting randomized sequence in a binary search tree

answered Jan 22, 2016 at 20:32

lrleon

2,6883 gold badges28 silver badges43 bronze badges

Collectives™ on Stack Overflow

Find a binary tree given only in-order traversal

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related