Reverse A Binary Tree (Left to Right)

Question

I was looking at interview questions and I recently came upon one that asked you how to reverse a general binary tree, like flip it from right to left.

So for example if we had the binary tree

     6
   /   \
  3     4
 / \   / \
7   3 8   1

Reversing it would create

     6
   /   \
  4     3
 / \   / \
1   8 3   7

You can see that the new tree is the mirror image of the original tree.

I haven't been able to think of a good implementation on how to solve this problem. Can anyone offer any good ideas?

Answer 1

You can use recursion. We swap the left and right child of a node, in-place, and then do the same for its children:

static void reverseTree(final TreeNode root) {
    final TreeNode temp = root.right;
    root.right = root.left;
    root.left = temp;
    
    if (root.left != null) {
        reverseTree(root.left);
    }
    
    if (root.right != null) {
        reverseTree(root.right);
    }
}

To handle the case where the parameter root may be null:

static void reverseTree(final TreeNode root) {
    if (root == null) {
        return;
    }
    
    final TreeNode temp = root.right;
    root.right = root.left;
    root.left = temp;
    
    reverseTree(root.left);
    
    reverseTree(root.right);
}