Decode the Coding Interview in Scala: Real-World Examples/

...

/

Invert Binary Tree

Invert Binary Tree

Understand and solve the interview question "Invert Binary Tree".

We'll cover the following...

Description

In this lesson, your task is to invert a given a binary tree, T.

Let’s look at an example below:

class TreeNode(var value:Int=0, var left:TreeNode=null, var right:TreeNode=null) {
}
object Solution {
  def invertTree(root: TreeNode): TreeNode = {
    //write your code here
    root
  }
}
Invert binary tree

Solution

We can solve this problem using depth-first search (DFS).

The inverse of an empty tree is the empty tree. To invert tree T with root and subtrees left and right, we keep root the same and invert the right and left subtrees.

Let’s review the implementation below:

import scala.collection.mutable.ListBuffer
object Main {
  class TreeNode(var value:Int=0, var left:TreeNode=null, var right:TreeNode = null){
  }
  class Utility {
    def helper(node: TreeNode, level: Int, levels: ListBuffer[ListBuffer[Int]]): Unit = { // start the current level
      if (levels.size == level)
        levels.addOne(new ListBuffer[Int])
      // fulfil the current level
      levels(level).addOne(node.value)
      // process child nodes for the next level
      if (node.left != null)
        helper(node.left, level + 1, levels)
      if (node.right != null)
        helper(node.right, level + 1, levels)
    }
    def levelOrder(root: TreeNode): ListBuffer[ListBuffer[Int]] = {
      val levels = new ListBuffer[ListBuffer[Int]]
      if (root == null)
        return levels
      helper(root, 0, levels)
      levels
    }
    def print(root: TreeNode): Unit = {
      println(levelOrder(root))
    }
  }
  def invertTree(root: TreeNode): TreeNode = {
    if (root == null) return root
    val right = invertTree(root.right)
    val left = invertTree(root.left)
    root.left = right
    root.right = left
    root
  }
  def main(args: Array[String]): Unit = {
    val root = new TreeNode(1)
    root.left = new TreeNode(2)
    root.right = new TreeNode(3)
    root.left.left = new TreeNode(4)
    root.left.right = new TreeNode(5)
    root.right.left = new TreeNode(6)
    root.right.right = new TreeNode(7)
    new Utility().print(invertTree(root))
  }
}
Invert binary tree

Complexity measures

Time Complexity Space Complexity
...