Skip to content

226. Invert Binary TreeΒΆ

Problem Link

Inverting binary tree applies uniformly at every node: the left and right children simply need to be swapped. Since this operation depends on the same transformation being applied to each subtree, the problem fits a recursive approach.

Starting from the root, we think in terms of subproblems: if we already know how to invert the left and right subtrees, then inverting the current tree is just a matter of swapping those two results. This leads directly to a depth-first traversal where each node waits for its children to be processed before performing the swap.

The base case occurs when we reach a None node, which requires no action. As the recursion unwinds, each node swaps its left and right pointers, effectively inverting the tree from the bottom up.

Pseudocode 
    if node is null:
    return null
    left = invertTree(node.left)
    right = invertTree(node.right)
    node.left = right
    node.right = left
    return node
Runtime Complexity

Time: \(O(n)\), where \(n\) is the number of nodes in the tree

Space: O(h) due to recursion stack, where \(h\) is the height of the tree

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None

        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root

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