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

Invert Binary Tree

Explore how to invert a binary tree by applying depth-first search techniques. This lesson guides you through inverting the left and right subtrees recursively, helping you understand the problem's time and space complexity for 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

Javascript (babel-node)
import {TreeNode} from './TreeNode.js'
function invertTree(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:

Javascript (babel-node)
function invertTree(root){
    if (root == null)
      return root
    var right = invertTree(root.right)
    var left = invertTree(root.left)
    root.left = right
    root.right = left
    return root
}
// Driver Code
var 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)
printTree(invertTree(root))
Invert binary tree

Complexity measures

Time Complexity Space Complexity
...