Invert Binary Tree — DSA · Engineering Playbook

Invert Binary Tree

Recursively swap each node's children — a four-line classic.

Easy

Time O(n) Space O(h)

May 16, 2026 2 min read

Problem#

Given the root of a binary tree, invert it (left subtree becomes right and vice versa at every node) and return its root.

Examples#

[4,2,7,1,3,6,9] → [4,7,2,9,6,3,1]
[2,1,3] → [2,3,1]
[] → []

Constraints#

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

Approach#

Recursively invert left and right subtrees, then swap them.

Solution#

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return nullptr;
        TreeNode* l = invertTree(root->left);
        TreeNode* r = invertTree(root->right);
        root->left = r;
        root->right = l;
        return root;
    }
};

func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    l := invertTree(root.Left)
    r := invertTree(root.Right)
    root.Left = r
    root.Right = l
    return root
}

from typing import Optional

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

function invertTree(root) {
    if (!root) return null;
    const l = invertTree(root.left);
    const r = invertTree(root.right);
    root.left = r;
    root.right = l;
    return root;
}

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

function invertTree(root: TreeNode | null): TreeNode | null {
    if (!root) return null;
    const l = invertTree(root.left);
    const r = invertTree(root.right);
    root.left = r;
    root.right = l;
    return root;
}

Editorial#

Each node is visited exactly once. The swap happens after recursion so subtree pointers are already inverted — equivalent to swapping first then recursing, both correct.

Complexity#

Time: O(n).
Space: O(h) recursion stack.

Concept revision#

Symmetric Tree

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#