Interview challenge · easy · binary-tree, recursion, dfs

Invert Binary Tree

The challenge

Given the root of a binary tree, invert the tree (mirror it, so every left child becomes a right child and vice versa) and return its root.

Example

      4                 4
    /   \             /   \
   2     7    ->     7     2
  / \   / \         / \   / \
 1   3 6   9       9   6 3   1

Idea: recursion. Inverting a tree is swapping the two children of the root and inverting each subtree. Time O(n), space O(h) for the call stack.

The solution

1# Invert Binary Tree - ayotl.dev
2class T:
3    def __init__(self, v, l=None, r=None):
4        self.v, self.l, self.r = v, l, r
5
6
7def invert(t):
8    if t:
9        # swap the children, inverted
10        t.l, t.r = invert(t.r), invert(t.l)
11    return t
12
13
14def levels(t):
15    # read the tree level by level
16    out, q = [], [t]
17    while q:
18        n = q.pop(0)
19        out.append(n.v)
20        q += [c for c in (n.l, n.r) if c]
21    return out
22
23
24root = T(4, T(2, T(1), T(3)),
25         T(7, T(6), T(9)))
26print(levels(root))
27print(levels(invert(root)))

$ python3 invert_binary_tree.py

[4, 2, 7, 1, 3, 6, 9]

[4, 7, 2, 9, 6, 3, 1]

The video

Watch on YouTube →