TheLazy.Dev
Portfolio GitHub

Blog

binary |tree |invert |python

Inverting a Binary Tree

sbalasa

Santhosh Balasa

Posted on December 23, 2021

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
💖 💪 🙅 🚩
sbalasa
Santhosh Balasa

Posted on December 23, 2021

Join Our Newsletter. No Spam, Only the good stuff.

Sign up to receive the latest update from our blog.

Related

Inverting a Binary Tree
binary Inverting a Binary Tree

December 23, 2021