object Main extends App {
  val n: Int = io.StdIn.readInt()
  val Seq(i, l, r): Seq[Int] = io.StdIn.readLine().split(" ").map(_.toInt)
  val tree =
    (1 until n).foldLeft(Node(i, Leaf(l), Leaf(r)): BinaryTree[Int]) { (t, _) =>
      val Seq(i,l,r): Seq[Int] = io.StdIn.readLine().split(" ").map(_.toInt)
      t.insert(i,l,r)
    }

  println(s"Preorder\n ${tree.preorder.mkString(" ")}\nInorder\n ${tree.inorder.mkString(" ")}\nPostorder\n ${tree.postorder.mkString(" ")}")

  sealed trait BinaryTree[T] extends {
    def preorder: Seq[T]
    def inorder: Seq[T]
    def postorder: Seq[T]
    def insert(x: T, l: T, r: T): BinaryTree[T]
  }
  case class Leaf[T](v: T) extends BinaryTree[T] {
    def insert(x: T, l: T, r: T): BinaryTree[T] = if (v == x) Node(v, Leaf(l), Leaf(r)) else this
    def preorder:  Seq[T] = Seq()
    def inorder:   Seq[T] = Seq()
    def postorder: Seq[T] = Seq()
  }
  case class Node[T](v: T, left: BinaryTree[T], right: BinaryTree[T]) extends BinaryTree[T] {
    def insert(x: T, l: T, r: T): BinaryTree[T] = Node(v,left.insert(x,l,r), right.insert(x,l,r))
    def preorder: Seq[T] = v +: (left.preorder ++ right.preorder)
    def inorder: Seq[T]  = left.inorder ++ (v +: right.inorder)
    def postorder: Seq[T] = left.postorder ++ right.postorder ++ Seq(v)
  }
}
