Decode the Coding Interview in Kotlin: 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:

Coding Exercise

main.kt
TreeNode.kt
internal object Solution {
    fun invertTree(root: TreeNode): TreeNode {
        return 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:

main.kt
TreeNode.kt
internal object Solution {
    fun invertTree(root: TreeNode?): TreeNode? {
        if (root == null) {
            return root
        }
        val right: TreeNode? = Solution.invertTree(root.right)
        val left: TreeNode? = Solution.invertTree(root.left)
        root.left = right
        root.right = left
        return root
    }
}
fun main() {
    val root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left!!.left = TreeNode(4)
    root.left!!.right = TreeNode(5)
    root.right!!.left = TreeNode(6)
    root.right!!.right = TreeNode(7)
    Utility.print(Solution.invertTree(root))
}
Invert binary tree

Complexity measures

Time Complexity Space Complexity
...