Invert Binary Tree

• easy
• Problem URL

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

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

Solution

Use a recursive function to invert the tree. The function will swap the left and right child of the current node, and then recursively invert the left and right child nodes.

Implementation

JavaScript

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

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

  root.left = right;
  root.right = left;

  return root;
}

TypeScript

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

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

  root.left = right;
  root.right = left;

  return root;
}

Go

func invertTree(root *TreeNode) *TreeNode {
  if root == nil {
    return root
  }

  left := invertTree(root.Left)
  right := invertTree(root.Right)

  root.Left = right
  root.Right = left

  return root
}

Pseudocode

1. If the root is null, return null
2. Recursively invert the left and right child nodes
3. Swap the left and right child nodes
4. Return the root node

Complexity Analysis

• The time complexity of this algorithm is O(N), where N is the number of nodes in the binary tree.
• The space complexity of this algorithm is O(N), where N is the number of nodes in the binary tree.