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?
6 Answers
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); } 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; } 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.
3You can recursively swap the left and right nodes as below;
// helper method private static void reverseTree(TreeNode<Integer> root) { reverseTreeNode(root); } private static void reverseTreeNode(TreeNode<Integer> node) { TreeNode<Integer> temp = node.left; node.left = node.right; node.right = temp; if(node.left != null) reverseTreeNode(node.left); if(node.right != null) reverseTreeNode(node.right); } Demonstration Code for Java
import java.util.LinkedList; import java.util.Queue; public class InvertBinaryTreeDemo { public static void main(String[] args) { // root node TreeNode<Integer> root = new TreeNode<>(6); // children of root root.left = new TreeNode<Integer>(3); root.right = new TreeNode<Integer>(4); // grand left children of root root.left.left = new TreeNode<Integer>(7); root.left.right = new TreeNode<Integer>(3); // grand right childrend of root root.right.left = new TreeNode<Integer>(8); root.right.right = new TreeNode<Integer>(1); System.out.println("Before invert"); traverseTree(root); reverseTree(root); System.out.println("\nAfter invert"); traverseTree(root); } // helper method private static void reverseTree(TreeNode<Integer> root) { reverseTreeNode(root); } private static void reverseTreeNode(TreeNode<Integer> node) { TreeNode<Integer> temp = node.left; node.left = node.right; node.right = temp; if(node.left != null) reverseTreeNode(node.left); if(node.right != null) reverseTreeNode(node.right); } // helper method for traverse private static void traverseTree(TreeNode<Integer> root) { Queue<Integer> leftChildren = new LinkedList<>(); Queue<Integer> rightChildren = new LinkedList<>(); traverseTreeNode(root, leftChildren, rightChildren); System.out.println("Tree;\n*****"); System.out.printf("%3d\n", root.value); int count = 0; int div = 0; while(!(leftChildren.isEmpty() && rightChildren.isEmpty())) { System.out.printf("%3d\t%3d\t", leftChildren.poll(), rightChildren.poll()); count += 2; div++; if( (double)count == (Math.pow(2, div))) { System.out.println(); count = 0; } } System.out.println(); } private static void traverseTreeNode(TreeNode<Integer> node, Queue<Integer> leftChildren, Queue<Integer> rightChildren) { if(node.left != null) leftChildren.offer(node.left.value); if(node.right != null) rightChildren.offer(node.right.value); if(node.left != null) { traverseTreeNode(node.left, leftChildren, rightChildren); } if(node.right != null) { traverseTreeNode(node.right, leftChildren, rightChildren); } } private static class TreeNode<E extends Comparable<E>> { protected E value; protected TreeNode<E> left; protected TreeNode<E> right; public TreeNode(E value) { this.value = value; this.left = null; this.right = null; } } } Output
Before invert Tree; ***** 6 3 4 7 3 8 1 After invert Tree; ***** 6 4 3 1 8 3 7 The recursion function can be very simple as shown below:
public Node flipTree(Node node) { if(node == null) return null; Node left = flipTree(node.left); Node right = flipTree(node.right); node.left = right; node.right = left; return node; } I've seen most of the answers aren't focussing on null pointer issues.
public static Node invertBinaryTree(Node node) { if(node != null) { Node temp = node.getLeftChild(); node.setLeftChild(node.getRightChild()); node.setRigthChild(temp); if(node.left!=null) { invertBinaryTree(node.getLeftChild()); } if(node.right !=null) { invertBinaryTree(node.getRightChild()); } } return node; } In the code above we are making recursive calls only if the left/right child of the root node isn't null. Its one of the fastest approach!
