Input : Inorder -> 4 2 5 1 3 Preorder -> 1 2 4 5 3 Postorder -> 4 5 2 3 1 Output : Yes Exaplanation : All of the above three traversals are of the same tree 1 / 2 3 / 4 5 Input : Inorder -> 4 2 5 1 3 Preorder -> 1 5 4 2 3 Postorder -> 4 1 2 3 5 Output : No
The most basic approach to solve this problem will be to first construct a tree using two of the three given traversals and then do the third traversal on this constructed tree and compare it with the given traversal. If both of the traversals are same then print Yes otherwise print No. Here, we use Inorder and Preorder traversals to construct the tree. We may also use Inorder and Postorder traversal instead of Preorder traversal for tree construction. You may refer to this post on how to construct tree from given Inorder and Preorder traversal. After constructing the tree, we will obtain the Postorder traversal of this tree and compare it with the given Postorder traversal.
Below is the implementation of above approach:
Time Complexity : O( n * n ), where n is number of nodes in the tree.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.