DEV Community 👩‍💻👨‍💻

Cover image for Inverting a Binary Tree
Santhosh Balasa
Santhosh Balasa

Posted on • Updated on

Inverting a Binary Tree

Binary Tree:

         (4)
        /  \
       /    \
     (2)    (7)                  
     / \    /  \
    /   \ (6)  (9)
  (1)   (3)
Enter fullscreen mode Exit fullscreen mode

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

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

Top comments (0)

Want to rep DEV and be comfy at the same time?

Check out our classic DEV shirt — available in multiple colors.