Inverting a Binary Tree

#binary #tree #invert #python

Binary Tree:

         (4)
        /  \
       /    \
     (2)    (7)                  
     / \    /  \
    /   \ (6)  (9)
  (1)   (3)

Inverting a Binary tree means mirroring the tree, i.e, swapping the children from left to right and vice versa.

Inverted Binary Tree:

         (4)                         
        /  \
       /    \
     (7)    (2)                    
     / \    /  \
    /   \ (3)  (1)
  (9)   (6)

This can be easily achieved using recursion,

Code:

tree = {
    4: [2, 7],
    2: [1, 3],
    7: [6, 9],
    1: [],
    3: [],
    6: [],
    9: []
}


def invert_tree(tree, node, path=[]):
    if tree[node]:
        path.extend(tree[node][::-1])
        invert_tree(tree, tree[node][1], path)
        invert_tree(tree, tree[node][0], path)
    return [node] + path