Search⌘ K
Home
Courses
Decode the Coding Interview in Go: Real-World Examples

Invert Binary Tree

Explore how to invert a binary tree by recursively swapping its left and right subtrees using depth-first search. This lesson helps you understand the implementation details and analyze the operation's time and space complexities, improving your grasp of binary tree manipulations in coding interviews.

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

Go (1.6.2)
package main
import (
  "fmt"
  "strconv"
  "encoding/json"
)
type TreeNode struct{
    val int
    left *TreeNode
    right *TreeNode
}
func invertTree(root *TreeNode) *TreeNode{
    // write your code here
    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:

Go (1.6.2)
package main
import (
  "fmt"
  "strconv"
)
type TreeNode struct{
    val int
    left *TreeNode
    right *TreeNode
}
func invertTree(root *TreeNode) *TreeNode{
    if root == nil {
        return root
    }
    right := invertTree(root.right)
    left := invertTree(root.left)
    root.left = right
    root.right = left
    return root
}
func main() {
    root := &TreeNode{val: 1}
    root.left = &TreeNode{val: 2}
    root.right = &TreeNode{val: 3}
    root.left.left = &TreeNode{val: 4}
    root.left.right = &TreeNode{val: 5}
    root.right.left = &TreeNode{val: 6}
    root.right.right = &TreeNode{val: 7}
    print(invertTree(root))
}
Invert binary tree

Complexity measures

Time Complexity Space Complexity
...