How to mirror binary tree?

Question

I need to mirror binary tree in Scala. I think it have to work like this:

sealed trait BT[+A]
case object Empty extends BT[Nothing]
case class Node[+A](elem:A, left:BT[A], right:BT[A]) extends BT[A]

def mirrorTree[A](bt: BT[A]): BT[A] = bt match {
  case Empty => Empty
  case Node(root, left, right) => Node(root, right, left)
}

val t = Node(1,Node(2,Empty,Node(3,Empty,Empty)),Empty)
mirrorTree(t)

But it returns me only swapped first level, I have to call function in recursive way for left and right subtree, but I do not know how to do it if I have to return tree from function, so I can not use operators like for lists.

as a side note, you should mark your `case class` **final**!, [reference](https://stackoverflow.com/questions/34561614/should-i-use-the-final-modifier-when-declaring-case-classes). — Luis Miguel Mejía Suárez, Dec 03 '18 at 16:07

score 3 · Accepted Answer · answered Dec 03 '18 at 07:29

3

If you want to mirror it all then do:

case Node(root, left, right) => Node(root, mirrorTree(right), mirrorTree(left))

answered Dec 03 '18 at 07:29

talex

17,973
3
29
66

score 3 · Answer 2 · answered Dec 03 '18 at 07:32

You were very close, you just needed to call the method recursively, to ensure that the sub-trees were mirrored before building the rest of the tree.

sealed trait BT[+A]
case object Empty extends BT[Nothing]
case class Node[+A](elem:A, left:BT[A], right:BT[A]) extends BT[A]

def mirrorTree[A](bt: BT[A]): BT[A] = bt match {
  case Empty => Empty
  case Node(root, left, right) => 
    val newLeft = mirrorTree(right) 
    val newRight = mirrorTree(left)
    Node(root, newLeft,newRight)
}

val t = Node(1,Node(2,Empty,Node(3,Empty,Node(4,Empty,Empty))),Empty)


mirrorTree(t)  // Node(1,Empty,Node(2,Node(3,Node(4,Empty,Empty),Empty),Empty))

How to mirror binary tree?

2 Answers2