TREEORD  Tree _order
Description
A tree is a connected acyclic graph.
A binary tree is a tree for which each node has a left child, a right child, both, or neither, e.g.
1 / \ 2 3 / \ \ 4 5 6
There are three common ways to recursively traverse such a tree.
 Preorder: parent, left subtree, right subtree
 Postorder: left subtree, right subtree, parent
 Inorder: left subtree, parent, right subtree
Given preorder, postorder, and inorder traversals, determine if they can be of the same binary tree.
For example,
1 2 4 5 3 6 4 5 2 6 3 1 4 2 5 1 3 6are the preorder, postorder, and inorder traversals of the tree above.
But
1 2 4 5 3 6 4 5 2 6 1 3 4 2 5 1 6 3cannot be the preorder, postorder, and inorder tranversals of the same binary tree.
Input
The first line is the number of nodes in each traversal, 0 < N <= 8000.
The second line is the N space seperated nodes of the preorder traveral.
The third line is the N space separated nodes of the postorder traversal.
The fourth line is the N space separated nodes of the inorder traversal.
The second line is the N space seperated nodes of the preorder traveral.
The third line is the N space separated nodes of the postorder traversal.
The fourth line is the N space separated nodes of the inorder traversal.
Each traversal is a sequence of the nodes, numbered 1 to N, without repitition.
Output
Print "yes" if all three traversals can be of the same tree, and "no" otherwise.
Input  Input 

6 1 2 4 5 3 6 4 5 2 6 3 1 4 2 5 1 3 6 
6 1 2 4 5 3 6 4 5 2 6 1 3 4 2 5 1 6 3 
Output  Output 
yes 
no 
hide comments
ankit_code2799:
20200513 20:41:37
AC in the first go. Try using a map for making use to inorder and postorder traversal to generate the expected preorder traversal and comparing it with the given preorder. Last edit: 20200619 08:47:35 

jpgmoreira:
20200310 23:33:48
Very interesting problem!!! 

manthan913:
20190822 14:34:56
@saltyfish233 how


drexor:
20181205 04:50:50
Its embarrasing but I did 4 WA because I was printing 'Yes' instead of 'yes'. 

cyber_sm0ke:
20180628 12:40:29
can anyone help in solving this problem without building tree .


agent063_47:
20180503 16:04:48
Solved by Tree Construction 

saltyfish233:
20171119 13:21:16
I don`t use recursion but I use stack to solve it :D 

kspoj:
20171111 18:05:40
Wow..This.Is.Cool


Pranv Gupta:
20170331 11:37:21
nice question, but wondering if there is only ONE testcase of this problem 

deerishi:
20161022 23:43:56
MY 100th! 0.00 sec.!! Funny thing : With and without Tree construction with Fast IO accepted in 0.00s !! Without tree construction is cooler though. Last edit: 20161023 00:57:34 
Added by:  BYU Admin 
Date:  20140223 
Time limit:  0.5s3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 