Coding Interview Questions | Invert Binary Tree

December 19th, 2023

Introduction:

This summary will talk about my solution to the invert binary tree problem as seen on leetcode here.

Solution:

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

  // Use a queue to implement reverse breadth-first search
  const nodeQueue = [root];

  while (nodeQueue.length > 0) {
    const currentNode = nodeQueue.shift()!;

    const temp = currentNode.left;
    currentNode.left = currentNode.right;
    currentNode.right = temp;

    // Enqueue the left and right children of the current node
    if (currentNode.left) {
      nodeQueue.push(currentNode.left);
    }
    if (currentNode.right) {
      nodeQueue.push(currentNode.right);
    }
  }

  return root;
}

Summary:

• The solution above aims to invert a binary tree by applying a reverse breadth-first search approach, using a while loop.

• The function utilizes a queue to implement the reverse breadth-first search, ensuring a level-by-level exploration of the binary tree.

• Within the while loop, nodes are dequeued, and their left and right children are swapped using a temporary variable.

• The left and right children of each node are then enqueued back into the queue for subsequent exploration.

• The while loop continues until all nodes are visited, ensuring a comprehensive inversion across all levels of the binary tree.

• The final output is the root of the inverted binary tree, where the solution was achieved with a time complexity of O(n) as each node in the tree was visited once in the inversion process.