Search⌘ K
AI Features
Home
Courses
Decode the Coding Interview in Scala: Real-World Examples

Invert Binary Tree

Explore how to invert a binary tree by applying depth-first search techniques. Understand the recursive process of swapping left and right subtrees, and analyze the problem's time and space complexities to prepare for coding interviews effectively.

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:

Scala
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:

Scala
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
...