CODEWITHSUNDEEP
cdata-structures
codey modey
codey modey

Reputation: 983

locate root node in binary tree stored in array in inorder

Example Tree 

2 -> root
1 -> Left
3 -> right

stored in array in in order [1, 2, 3]

How to retrieve the root node knowing that the tree is stored in inorder?

According to me all three as possible candidates of root node.

Upvotes: 1

Views: 157

Answers (1)

Bernhard Barker
Bernhard Barker

Reputation: 55609

Indeed all 3 are possible candidates.

Here are possible trees that would result in the given in-order traversal:

 1           2           3
  \         / \         /
   2       1   3       2
    \                 /
     3               1

An in-order traversal isn't necessarily sufficient to uniquely identify a tree (and thus consistently identify the root). Assuming unique tree elements, you need either a pre-order or post-order traversal paired with an in-order traversal.

Reference - Which combinations of pre-, post- and in-order sequentialisation are unique?

Upvotes: 1

Related Questions