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

Invert Binary Tree

Explore how to invert a binary tree using depth-first search in Kotlin. Understand the recursive approach to swapping left and right subtrees, along with the time and space complexity analysis, 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:

Coding Exercise

Files
main.kt
TreeNode.kt
Kotlin 1.5
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:

Files
main.kt
TreeNode.kt
Kotlin 1.5
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
...