Reverse A Binary Tree (Left to Right) [closed]

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);
}

Answer 2

Reverse a binary tree in O(1) in C/C++.

struct NormalNode {
  int value;
  struct NormalNode *left;
  struct NormalNode *right;
};

struct ReversedNode {
  int value;
  struct ReversedNode *right;
  struct ReversedNode *left;
};

struct ReversedNode *reverseTree(struct NormalNode *root) {
  return (struct ReversedNode *)root;
}

Answer 3

There are a couple interesting parts to this question. First, since your language is Java, you're most likely to have a generic Node class, something like this:

class Node<T> {
    private final T data;
    private final Node left;
    private final Node right;
    public Node<T>(final T data, final Node left, final Node right) {
        this.data  = data;
        this.left  = left;
        this.right = right;
    }
    ....
}

Secondly, reversing, sometimes called inverting, can be done either by mutating the left and right fields of the node, or by creating a new node just like the original but with its left and right children "reversed." The former approach is shown in another answer, while the second approach is shown here:

class Node<T> {
    // See fields and constructor above...

    public Node<T> reverse() {
        Node<T> newLeftSubtree = right == null ? null : right.reverse();
        Node<T> newRightSubtree = left == null ? null : left.reverse();
        return Node<T>(data, newLeftSubtree, newRightSubtree); 
    }
}

The idea of not mutating a data structure is one of the ideas behind persistent data structures, which are pretty interesting.