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.
  1. Pre-order: parent, left subtree, right subtree
  2. Post-order: left subtree, right subtree, parent
  3. In-order: left subtree, parent, right subtree
Given pre-order, post-order, and in-order 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 6
are the pre-order, post-order, and in-order traversals of the tree above.
But
1 2 4 5 3 6
4 5 2 6 1 3
4 2 5 1 6 3
cannot be the pre-order, post-order, and in-order traversals 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 separated nodes of the pre-order traversal.
The third line is the N space separated nodes of the post-order traversal.
The fourth line is the N space separated nodes of the in-order traversal.
Each traversal is a sequence of the nodes, numbered 1 to N, without repetition.

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: 2020-05-13 20:41:37

AC in the first go. Try using a map for making use to inorder and postorder traversal to generate the expected pre-order traversal and comparing it with the given pre-order.

Last edit: 2020-06-19 08:47:35
jpgmoreira: 2020-03-10 23:33:48

Very interesting problem!!!

manthan913: 2019-08-22 14:34:56

@saltyfish233 how

drexor: 2018-12-05 04:50:50

Its embarrasing but I did 4 WA because I was printing 'Yes' instead of 'yes'.

cyber_sm0ke: 2018-06-28 12:40:29

can anyone help in solving this problem without building tree .

Email Id : shivi98g@gmail.com

agent063_47: 2018-05-03 16:04:48

Solved by Tree Construction

saltyfish233: 2017-11-19 13:21:16

I don`t use recursion but I use stack to solve it :D

kspoj: 2017-11-11 18:05:40

Wow..This.Is.Cool
Learnt some.... :0 :D

Pranv Gupta: 2017-03-31 11:37:21

nice question, but wondering if there is only ONE testcase of this problem

deerishi: 2016-10-22 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: 2016-10-23 00:57:34

Added by:BYU Admin
Date:2014-02-23
Time limit:0.5s-3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64