Invert a Binary Tree

Jul 29, 2021

In an inverted binary tree, each node in the original is swapped with the corresponding node on the other side.

You can also think of it as rotating the tree on an axis right down the middle.

Example: adsf

Here’s the same tree, inverted.

adsf

Like most tree problems, it’s best handled recursively. You just

Swap
Recurse to the left child
Recurse to the right child

1
def invertBinaryTree(tree):
2
    # This is why I use Python for stuff like this
3
  tree.left,tree.right = tree.right,tree.left
4

5
    if (tree.left is not None):
6
    invertBinaryTree(tree.left)
7
  if (tree.right is not None):
8
    invertBinaryTree(tree.right)
9

10
class BinaryTree:
11
    def __init__(self, value):
12
        self.value = value
13
        self.left = None
14
        self.right = None

It’s surprisingly simple.

Wow! You read the whole thing. People who make it this far sometimes want to receive emails when I post something new.

I also have an RSS feed.