How to Mirror a Binary Tree?

Given a binary tree like this:

 
    	    8
    	   /  \
    	  6   10
    	 / \  / \
    	5  7 9 11

Your task is to mirror it which becomes this:

    	    8
    	   /  \
    	  10   6
    	 / \  / \
    	11 9 7  5

The most elegant algorithm to mirror a binary tree is using recursion. We can recursively mirror left and right trees respectively and then swap the left and right trees.

public class Solution {
    public void Mirror(TreeNode root) {
        if (root == null) return;
        // make left tree also a mirror recursively
        Mirror(root.left);
        // make right tree also a mirror tree.
        Mirror(root.right);
        // swap left and right trees
        TreeNode t = root.left;
        root.left = root.right;
        root.right = t;        
    }
}

The time complexity is O(N) where each node will be visited constant time, and the space complexity through calling stacks via recursion is O(N)=O(h) which is the height of the tree.

It is said that this is one of the Google’s interview question, a simple one though.

–EOF (The Ultimate Computing & Technology Blog) —