Invert Binary Tree

Problem

https://leetcode.com/problems/invert-binary-tree/

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

Example 1:

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

Example 2:

Input: root = [2,1,3]
Output: [2,3,1]

Example 3:

Input: root = []
Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 100].

• -100 <= Node.val <= 100

Pattern

Tree, Depth-First Search, Breadth-First Search, Binary Tree

Approaches

Recursive

Explanation

Observe that when we invert the tree, we can do it in 2 steps: 1. Swap the left and right children of the root. 2. Invert the left and right subtrees. This gives a recursive algorithm to invert a binary tree.

Code

from __future__ import annotations

from collections import deque


class TreeNode:
    """Node in a binary tree."""

    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    @classmethod
    def from_list(cls, vals: list[int | None]) -> TreeNode | None:
        if not vals:
            return None

        root = cls(vals[0])
        queue = deque([root])
        children = iter(vals[1:])

        while queue:
            node = queue.popleft()
            for side in ("left", "right"):
                val = next(children, None)
                if val is not None:
                    child = cls(val)
                    setattr(node, side, child)
                    queue.append(child)

        return root

    def __repr__(self) -> str:
        return f"TreeNode({self.val}, {self.left}, {self.right})"


def invertTree(root: TreeNode | None) -> TreeNode | None:
    """Inverts a binary tree by swapping the left and right nodes."""
    if root is None:
        return None

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

Test

>>> from invert_binary_tree__recursive import TreeNode, invertTree
>>> root = TreeNode.from_list([4, 2, 7, 1, 3, 6, 9])
>>> invertTree(root)
TreeNode(4, TreeNode(7, TreeNode(9, None, None), TreeNode(6, None, None)), TreeNode(2, TreeNode(3, None, None), TreeNode(1, None, None)))
>>> root = TreeNode.from_list([2, 1, 3])
>>> invertTree(root)
TreeNode(2, TreeNode(3, None, None), TreeNode(1, None, None))
>>> root = TreeNode.from_list([])
>>> invertTree(root) is None
True

Complexity

\(n\) is the number of nodes in the tree

Measure	Complexity	Notes
Time	\(O(n)\)	visit every node
Auxiliary Space	\(O(1)\)

class invert_binary_tree__recursive.TreeNode(val, left=None, right=None)

Bases: object

Node in a binary tree.

classmethod from_list(vals: list[int | None]) → TreeNode | None

invert_binary_tree__recursive.invertTree(root: TreeNode | None) → TreeNode | None

Inverts a binary tree by swapping the left and right nodes.