Day 66: Python Invert Binary Tree, Recursive Mirror Swap for Perfect Tree Symmetry (LeetCode #226 Style)

Source: Dev.to

Welcome to Day 66 of the #80DaysOfChallenges journey! This intermediate challenge focuses on inverting a binary tree by recursively swapping left and right children, transforming the structure into its mirror image while preserving values. It uses recursive traversal to flip subtrees, a fundamental technique for tree manipulations like symmetry checks or balancing. If you’re advancing from basic recursion to tree algorithms or prepping for interviews (LeetCode #226), this “Python invert binary tree” script demonstrates a function that’s elegant, in‑place, and easy to adapt for iterative versions.

💡 Key Takeaways from Day 66: Tree Inversion Function

1. Function Design: Recursive Swap and Base Case

def invert_tree(tree: dict, node):
    """Recursively invert the binary tree starting from the given node."""
    if node is None:
        return

    left, right = tree.get(node, (None, None))   # get left and right children
    tree[node] = (right, left)                   # swap children

    invert_tree(tree, left)   # invert left subtree
    invert_tree(tree, right)  # invert right subtree

• Base case returns when node is None.
• Children are retrieved with dict.get, defaulting to (None, None).
• The tuple is swapped, then the function recurses on both sub‑trees.
• Complexity: O(n) time, O(h) space (where h is the tree height).

2. Tree Structure: Dict‑Based Representation

tree = {
    "A": ("B", "C"),
    "B": ("D", "E"),
    "C": (None, "F"),
    "D": (None, None),
    "E": (None, None),
    "F": (None, None),
}

• Keys are node identifiers; values are (left_child, right_child) tuples.
• Simple and convenient for small trees without custom node classes.

3. Main Demo: Before/After Inversion

root = "A"                    # root of the tree

print("Original tree:")
print(tree)

invert_tree(tree, root)       # invert the tree in‑place

print("\nInverted tree:")
print(tree)

• The output shows the root’s children swapped (A becomes ("C", "B")) and the same transformation applied recursively to all sub‑trees.

🎯 Summary and Reflections

• Recursive pattern: base case → process (swap) → recurse children.
• Dict for trees: flexible representation when class‑based nodes aren’t needed.
• In‑place modification: avoids extra memory allocation.

Possible extensions include an iterative version using a stack or queue, or using the inversion to check tree symmetry by comparing the original and inverted structures.

🚀 Next Steps and Resources

• Source Code for Challenge #66: scripts/invert_binary_tree.py
• Main Repository: 80-days-of-challenges
• Daily Updates: Twitter/X (@Shahrouzlogs)