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: sprakash24oct
linkedin

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 :)