Coding problem · Easy · Trees

Invert Binary Tree

Easy Algorithms & data structures Seen at Google, Amazon

Given the root of a binary tree, invert it (swap every node's left and right children) and return its root.

Example 1

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

Hints

Hint 1

Swap the children of the current node, then invert each subtree.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(h)

Recursively swap left and right at every node (pre- or post-order both work). Each node is visited once.

Reference solution

function invertTree(root) {
  if (!root) return null;
  [root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
  return root;
}

function invertTree(root: TreeNode | null): TreeNode | null {
  if (!root) return null;
  [root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
  return root;
}

def invert_tree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    if root:
        root.left, root.right = invert_tree(root.right), invert_tree(root.left)
    return root

<?php

function invertTree(?TreeNode $root): ?TreeNode
{
    if ($root !== null) {
        [$root->left, $root->right] = [invertTree($root->right), invertTree($root->left)];
    }
    return $root;
}

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode left = invertTree(root.left);
        root.left = invertTree(root.right);
        root.right = left;
        return root;
    }
}

Maximum Depth of Binary Tree · Easy
Binary Tree Level Order Traversal · Medium
Validate Binary Search Tree · Medium
Lowest Common Ancestor of a BST · Medium