LeetCode Meditations: Invert Binary Tree

Let's start with the description for Invert Binary Tree:

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

For example:

Although this one has a very simple recursive solution, let's see one approach that I come up with initially:

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *   val: number
 *   left: TreeNode | null
 *   right: TreeNode | null
 *   constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *     this.val = (val === undefined ? 0 : val)
 *     this.left = (left === undefined ? null : left)
 *     this.right = (right === undefined ? null : right)
 *   }
 * }
 */

function invertTree(root: TreeNode | null): TreeNode | null {
  let queue = [];
  queue.push(root);

  while (queue.length > 0) {
    let currentNode = queue[0];
    if (currentNode !== null) {
      queue.push(currentNode.left);
      queue.push(currentNode.right);
      [currentNode.left, currentNode.right] = [currentNode.right, currentNode.left];
    }

    queue.shift();
  }

  return root;
}

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *   val: number
 *   left: TreeNode | null
 *   right: TreeNode | null
 *   constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *     this.val = (val === undefined ? 0 : val)
 *     this.left = (left === undefined ? null : left)
 *     this.right = (right === undefined ? null : right)
 *   }
 * }
 */

function invertTree(root: TreeNode | null): TreeNode | null {
  let queue = [];
  queue.push(root);

  while (queue.length > 0) {
    let currentNode = queue[0];
    if (currentNode !== null) {
      queue.push(currentNode.left);
      queue.push(currentNode.right);
      [currentNode.left, currentNode.right] = [currentNode.right, currentNode.left];
    }

    queue.shift();
  }

  return root;
}

This version uses level-order traversal; we store the children of each node in a queue as we go through each level in the tree, and swap the node's left and right children.

Time and space complexity

Since we visit each node once, the time complexity is $O(n)$ . The space complexity will be proportionate to the size of the queue we keep, which holds a whole level at a time, which amounts to $O(n)$ overall.

Now, let's look at the recursive solution, which is much simpler:

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *   val: number
 *   left: TreeNode | null
 *   right: TreeNode | null
 *   constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *     this.val = (val === undefined ? 0 : val)
 *     this.left = (left === undefined ? null : left)
 *     this.right = (right === undefined ? null : right)
 *   }
 * }
 */

function invertTree(root: TreeNode | null): TreeNode | null {
  if (root === null) {
    return null;
  }

  [root.left, root.right] = [root.right, root.left];

  invertTree(root.left);
  invertTree(root.right);

  return root;
}

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *   val: number
 *   left: TreeNode | null
 *   right: TreeNode | null
 *   constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *     this.val = (val === undefined ? 0 : val)
 *     this.left = (left === undefined ? null : left)
 *     this.right = (right === undefined ? null : right)
 *   }
 * }
 */

function invertTree(root: TreeNode | null): TreeNode | null {
  if (root === null) {
    return null;
  }

  [root.left, root.right] = [root.right, root.left];

  invertTree(root.left);
  invertTree(root.right);

  return root;
}

Time and space complexity

The time complexity is $O(n)$ as we visit each node to swap its left and right children. The space complexity is also $O(h)$ —where $h$ is the height of the tree—because of the recursive calls to the function on each level.

Next up is Maximum Depth of Binary Tree. Until then, happy coding.

Eda Eren

LeetCode Meditations: Invert Binary Tree

Time and space complexity

Time and space complexity