AI Hints
Home›DSA in Python Tutorial›Trees, Lists and Grids
DSA in Python · Lesson 109 of 132

Practice: Invert a Binary Tree

A mirror image.

⏱ 2 min read▶ Video at 2:10:20🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Invert a binary tree, so it becomes its own mirror image. Every left child swaps places with its right child, all the way down. It's a short problem that tests whether you trust recursion.

Practice: Invert a Binary Tree
From the video: Practice: Invert a Binary Tree
  • A mirror image
  • Swap left and right
  • All the way down

Swap, then recurse

If the node is empty, there's nothing to do. Otherwise, swap its two children, and invert each of them in the same way. Three lines. We print the tree level by level, before and after. Run it. Each level now reads in reverse.

invert.pypython
from tree import sample
from levels import levels

def invert(node):
    if node:
        node.left, node.right = invert(node.right), invert(node.left)
    return node

root = sample()
print(levels(root))
print(levels(invert(root)))
Output
[[8], [3, 10], [1, 6, 14], [4, 7, 13]]
[[8], [10, 3], [14, 6, 1], [13, 7, 4]]
Also uses tree.py
class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value, self.left, self.right = value, left, right

def sample():
    return TreeNode(8,
        TreeNode(3, TreeNode(1), TreeNode(6, TreeNode(4), TreeNode(7))),
        TreeNode(10, None, TreeNode(14, TreeNode(13))))

PICTURE = '        8\n      /   \\\n     3     10\n    / \\      \\\n   1   6      14\n      / \\    /\n     4   7  13'
Also uses levels.py
from collections import deque
def levels(root):
    out, q = [], deque([root])
    while q:
        out.append([n.value for n in q])
        q = deque(c for n in q for c in (n.left, n.right) if c)
    return out

Recursion confidence

Interviewers like this problem because it's short, if you trust recursion, and long and messy if you don't. The pattern is the tree recipe again. Handle the empty case, do the work at this node, and let recursion handle the children. It visits each node once, so it's O of N.

keyvalue
Emptyreturn it
This nodeswap children
Childrenrecurse
CostO(n)

Summary

Swap the children, and recurse. Inverting a tree is three lines with recursion. Next, merging two sorted linked lists.

Key takeaways
  • Swap left and right
  • Recurse on both
  • O(n)
Next up: Practice: Merge Sorted Lists — one node at a time