EasyTreeDepth-First SearchBreadth-First SearchBinary Tree

Invert Binary Tree

1 approach, code in every language

You are given the root of a binary tree. Produce the mirror image of that tree by swapping the left and right child of every node, then return the (unchanged) root reference.

Inverting a tree means that at each node the two subtrees trade places, and this swap is applied all the way down to the leaves. After the operation, an in-order walk of the tree reads in reverse compared to the original.

Example 1

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

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

Every node keeps its value, but each node's left and right children are swapped, so 2 and 7 trade places, and beneath them 1/3 and 6/9 trade places as well.

Example 2

Input: root = [2,1,3]

Output: [2,3,1]

The root keeps value 2 while its children 1 and 3 swap sides.

Constraints

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

Recursive Swap

Invert each subtree, then swap the two children of the current node.

Loading animation…

Intuition

Inverting a tree is a naturally recursive task: the mirror of a tree is a node whose left child is the mirror of the original right subtree and whose right child is the mirror of the original left subtree. If we trust the recursion to correctly invert both subtrees, all that is left at each node is to swap the two returned references. The base case is an empty node, which is its own mirror. Because every node is visited exactly once and does a constant amount of work, the traversal is linear. This same structure can be rewritten iteratively with an explicit stack or queue if recursion depth is a concern.

Algorithm walkthrough

1If the current node is null, return null (an empty tree mirrors to an empty tree).
2Recursively invert the left subtree and capture the returned root.
3Recursively invert the right subtree and capture the returned root.
4Assign the inverted right subtree to node.left and the inverted left subtree to node.right.
5Return the current node so the parent call can attach it.
6The original root is returned once the top-level call unwinds.

Implementation

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)
        root.left = right
        root.right = left
        return root

Time

O(n)

Space

O(h)

Each of the n nodes is visited once. The recursion stack grows to the tree height h, which is O(log n) for a balanced tree and O(n) in the worst case (a skewed tree).

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Trees & BST

After the pattern

Now solve one you haven't seen.

Mirror The Splitter Harness is our own problem on the technique behind Invert Binary Tree: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free