import Data.List.Split
import qualified Data.Map as Map

--data Tree = Tree {node :: Int, left :: Tree, right :: Tree} | Emp
type Tree = Map.Map Int (Int,Int)

main = do
	ns <- getLoopValues
	let tree = createTree ns
	putStrLn "Preorder"
	putStr " " >> printList (preorder tree)
	putStrLn "Inorder"
	putStr " " >> printList (inorder tree)
	putStrLn "Postorder"
	putStr " " >> printList (postorder tree)

--リストの表示
printList [] = putStrLn ""
printList (x:[]) = putStrLn $ show x
printList (x:xs) = putStr (show (x) ++ " ") >> printList xs

--先行順巡回
preorder :: Tree -> [Int]
preorder tree = preorder_ (getRoot tree)
  where
    preorder_ (-1) = []
    preorder_ s = s:(preorder_ l) ++ (preorder_ r)
      where 
        (l,r) = tree Map.! s

--中間順巡回
inorder :: Tree -> [Int]
inorder tree = inorder_ (getRoot tree)
  where
    inorder_ (-1) = []
    inorder_ s = (inorder_ l) ++ s:(inorder_ r)
      where 
        (l,r) = tree Map.! s

--後行順巡回
postorder :: Tree -> [Int]
postorder tree = postorder_ (getRoot tree)
  where
    postorder_ (-1) = []
    postorder_ s = (postorder_ l) ++ (postorder_ r) ++ s:[]
      where 
        (l,r) = tree Map.! s

--木のルートを取得する
getRoot :: Tree -> Int
getRoot t = getRoot_ 0 t
  where
    getRoot_ n t = case getParent n t of
	                    Nothing -> n			--親が見つからなかった場合、今のノードがルート
	                    Just p -> getRoot_ p t --親が見つかった場合、さらにその親を取得する

--指定されたノードの親を取得する
getParent :: Int -> Tree -> Maybe Int
getParent c t = safeHead $ Map.keys $ Map.filter isChild t
  where 
    isChild (l,r)
      | l == c    = True
      | r == c    = True
      | otherwise = False

--headのMaybe版
safeHead []    = Nothing
safeHead (a:_) = Just a

--木（連想配列）を作る
createTree :: [(Int,Int,Int)] -> Tree
createTree ns = Map.fromList $ map (\(a,b,c) -> (a,(b,c))) ns

--画面入力の受付
getLoopValues :: IO([(Int,Int,Int)])
getLoopValues = do
    loopNum <- getInt
    lines <- getLoopValues' loopNum
    return $ map (\(a:b:c:_) -> (a,b,c)) $ map (map read) $ map (splitOn " ") $ lines

getLoopValues' :: Int -> IO([String])
getLoopValues' 0 = return []
getLoopValues' n = do
    v <- getLine
    vs <- getLoopValues' (n - 1)
    return $ v : vs

getInt :: IO (Int)
getInt = do
    str <- getLine
    return $ read str




