Menu

Invert Binary Tree

In this blog, we'll be solving the Invert Binary Tree problem on LeetCode.

Problem Overview

Given the root of a binary tree, invert the tree, and return its root.

Example 1:

Input: root = [4,2,7,1,3,6,9]

Output: [4,7,2,9,6,3,1]

The Approach

You can check the video below for a detailed explanation of the approach:

Inverting binary trees means swapping the left and right nodes of each node in the tree. We can do this recursively by traversing the tree and swapping the left and right nodes of each node.

  • Create a recursive function that takes in a node as an argument.
  • If the node is null, return the node.
  • Recursively call the function on the left and right nodes of the current node.
    • Store the return value of the left and right node in a variable.
  • Swap the left and right nodes of the current node.
  • Return the current node.

The solution

1const traverse = node => {
2    if (!node) return node
3

4    const leftNode = traverse(node.left)
5    const rightNode = traverse(node.right)
6

7    node.left = rightNode
8    node.right = leftNode
9

10    return node
11}
12

13var invertTree = function (root) {
14    return traverse(root)
15}

Complexity Analysis

  • Time Complexity: O(n) - We traverse the entire tree once.
  • Space Complexity: O(n) - The space occupied by the call stack is proportional to the height of the tree. In the worst case, the tree is linear, and the height is O(n).

Shameless Plug

I have made an Xbox landing page clone with React and Styled components. I hope you will enjoy it. Please consider like this video and subscribe to my channel.

That's it for this blog. I have tried to explain things simply. If you get stuck, you can ask me questions.

Contacts

Blogs you might want to read:

Videos might you might want to watch:

Previous PostSolve Maximum Depth of Binary Tree problem in Javascript
Next PostSolve LeetCode problem #125 Valid Palindrome