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

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 with tree flips (LeetCode #226), this "Python invert binary tree" script demonstrates a function that's elegant, in-place, and easy to adapt for iterative versions or graph symmetries.

💡 Key Takeaways from Day 66: Tree Inversion Function

This task features a recursive function that swaps children and recurses on subtrees, with a dict for tree representation and main for demo. It's a classic recursive pattern: base case on None, swap, recurse left/right. We'll detail: function with recursive swap, tree dict structure, and main with before/after print.

1. Function Design: Recursive Swap and Base Case

The invert_tree function takes tree dict and node, inverts in-place:

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 if None returns. Gets children with get (defaults None), swaps tuple. Recurses on both. For tree A:(B,C), flips to A:(C,B), then subtrees. O(n) time, O(h) space (height h).

2. Tree Structure: Dict-Based Representation

Example tree as dict node:(left, right):

tree = {

    "A": ("B", "C"),

    "B": ("D", "E"),

    "C": (None, "F"),

    "D": (None, None),

    "E": (None, None),

    "F": (None, None),

}

Dict keys nodes, values tuples for children. Simple for small trees, easy print.

3. Main Demo: Before/After Inversion

Script defines tree, prints original/inverted:

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)

Shows swap: A becomes ("C","B"), etc. In-place modifies dict.

🎯 Summary and Reflections

This tree inversion uses recursion for natural subtree flips. It reinforced:

• 
  Recursive pattern: Base None, process (swap), recurse children.


• 
  Dict for trees: Flexible for non-class nodes.


• 
  In-place mod: Efficient, no new structure.

Reflections: Iteration possible with stack/queue. For balance check, invert/compare.

Advanced Alternatives: Iterative with stack. Queue for level flip. Your tree flip? Share!

🚀 Next Steps and Resources

Day 66 mirrored trees recursively. In #80DaysOfChallenges? Iterated? Post!

• 
  Source Code for Challenge #66: scripts/invert_binary_tree.py
  


• 
  Main Repository: 80-days-of-challenges
  


• 
  Daily Updates: Twitter/X (@Shahrouzlogs)