DEV Community

Cover image for Inverting a Binary Tree
Santhosh Balasa
Santhosh Balasa

Posted on • Edited on

Inverting a Binary Tree

#binary #tree #invert #python

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)