91.invert-a-binary-tree.md

91. invert a binary tree

Problem

https://bigfrontend.dev/problem/invert-a-binary-tree

Problem Description

Can you invert a binary tree and get an offer from Google?

Inverting a node means swapping its left child and right child. You need to apply this to all nodes. As following figure illustrates.

        1                            1
      /   \                        /   \
     2     3                      3     2
    /       \      Invert        /       \
   4         5  ------------>   5         4
  / \       /                    \       / \
 6   7     8                      8     7   6
      \                                /
       9                              9

Understanding the problem

I am asked to write a function that is going to invert a Binary Tree and return the inverted version.

Approach

I am going to recursively traverse the Binary Tree. At each node, I am going to swap its child nodes and return the current node. If I get to a node that is equal to null, then it means I've reached a leaf node, just return the node. This is going to be the base case of the recursive function.

Solution

/**
 * @param {Node} node
 * @returns {Node}
 */
function invert(node) {
  if (!node) return node;

  const { left } = node;
  node.left = invert(node.right);
  node.right = invert(left);

  return node;
}