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.
Given binary tree
/ \ / \
4 5 6 7
invert and return
/ \ / \
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.
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
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 :)