# INVERT THE BINARY TREE

By: Saurav

2018-01-21 03:31:00 UTC

Given a binary tree, invert the binary tree and return it.
Look at the example for more details.

Example :
Given binary tree

1
/ \
2 3
/ \ / \
4 5 6 7
invert and return

1
/ \
3 2
/ \ / \
7 6 5 4

This is again a good practice for recursion.

The approach will be to use swapping among children of a node.

We can swap the data but we would have to deal with nil left or right child for a node.

So, it's better to swap the nodes themselves.

Algo:

The base case would be:
If a is nil return
if !a.left and !a.right -> No children -> return node a

Otherwise, swap the left and right subtrees.
Run the algo on the left and right subtrees.

Let's see in action:

``` def invertTree(a)

return if !a

return a if !a.left and !a.right

temp = a.left
a.left = a.right
a.right = temp

invertTree(a.left)
invertTree(a.right)

return a

end```

We can change the order from top down to bottom up as well if we use swapping after recursion in to the node's children:

``` def invertTree(a)

return if !a

return a if !a.left and !a.right
invertTree(a.left)
invertTree(a.right)

temp = a.left
a.left = a.right
a.right = temp

return a

end```

The only difference is the place at which the swapping happens in the stack call.

Another version as suggested by Srikiran would be:

```def invert_tree(root)
return unless root

swap_children(root)

invert_tree(root.left)
invert_tree(root.right)

root
end

def swap_children(root)
temp = root.right
root.right = root.left
root.left = temp
root
end```

Looks good to me.

### Let me know what you think! twitter: sprakash24octlinkedin

Owned & Maintained by Saurav Prakash

If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :) 