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, and \(d\) is the maximum depth of the tree.

Measure	Complexity	Notes
Time	\(O(n)\)	visit every node
Auxiliary Space	\(O(d)\)	recursive call stack

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.