DEV Community

Shahrouz Nikseresht
Shahrouz Nikseresht

Posted on

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

#challenge #python #datastructures #algorithms

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
Enter fullscreen mode Exit fullscreen mode

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),
}
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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!

Top comments (0)