In this article we have a look at another interesting problem related to binary tree. Given a binary tree we have to invert the tree and print it. We discuss different approaches to solve this problem along with their time and space complexities
The inversion of a binary tree or the invert of a binary tree means to convert the tree into it’s Mirror image. In simple terms, it is a tree whose left children and right children of all non-leaf nodes are swapped.
Note: The leaf nodes will also get interchanged. It is recommended to learn In-Order and Post Order traversal before proceeding with this problem.
Let us look at an example of a binary tree:
In the above figure we see the sample tree and it’s inverted or mirror version.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
Input: 20 / \ / \ 10 30 / \ / \ / \ / \ 5 15 25 35 Output: 20 / \ / \ 30 10 / \ / \ / \ / \ 35 25 5 15 |
Approach 1 (Recursive Approach)
Follow these steps:
- We basically do a Post-Order Traversal of our tree starting from the root where we traverse for the left subtree first and then the right subtree before processing the root.
- At time of processing the root of each node we swap their left and right child respectively if their children are not null.
- We also check if the given root of binary tree is null or not. Then, we continue traversing for the left and right subtrees accordingly. If, we are at a leaf node it does not have any children for which we return null indicating that no swapping is required.
- To verify the tree is inverted or not we do the In-Order traversal of tree before executing the function and again print the In-Order traversal after doing inversion. You can verify the output using any traversal algorithm.
Now, let’s look at the implementation of above in code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
//Class containing attributes of each node of tree class Node { int data; Node left, right; Node(int data) { this.data = data; left = null; right = null; } } class Tree { Node root; void invertTree(Node node) { if (node == null) return; //we call or recur for left subtrees then the right subtrees invertTree(node.left); invertTree(node.right); //swap the left and right child of each non-leaf node*/ Node temp=node.left; node.left = node.right; node.right = temp; } /* Helper function to test invertTree() by printing In-Order traversal*/ void printInOrder(Node node) { if (node == null) return; printInOrder(node.left); System.out.print(node.data + " "); printInOrder(node.right); } /*Driver code to test for sample tree*/ public static void main(String args[]) { /* creating a binary tree and entering the nodes */ Tree tree = new Tree(); tree.root = new Node(20); tree.root.left = new Node(10); tree.root.left.left = new Node(5); tree.root.left.right = new Node(15); tree.root.right = new Node(30); tree.root.right.left = new Node(25); tree.root.right.right = new Node(35); /* print inorder traversal of the input tree */ System.out.println("Inorder traversal of Input Tree is :"); tree.printInOrder(tree.root); System.out.println(); System.out.println(); /* convert tree to its mirror */ tree.invertTree(tree.root); /* Inorder traversal of the Inverted Binary tree */ System.out.println("Inorder traversal of Inverted Tree is : "); tree.printInOrder(tree.root); } } |
Output:
|
1 2 3 4 5 |
Inorder traversal of Input Tree is : 5 10 15 20 25 30 35 Inorder traversal of Inverted Tree is : 35 30 25 20 15 10 5 |
You can see the difference in output. The In-Order traversal for the given input tree displays output in sorted order and the In-order traversal of the Inverted tree gives output in reverse sorted order.
Time Complexity: We just traverse all the nodes present in tree so the time complexity will be O(n).
Space Complexity: If we consider the system stack space for each recursive call then complexity is O(n) otherwise it is O(1).
Approach 2 (Iterative Approach)
The main idea is to do a Level Order Traversal of the tree using a Queue. We enqueue the root first into the Queue. While we traverse all the nodes at a particular level we swap the left child and right child of each node. After this, we add the left and right child child of the current node into our queue to continue the level order traversal.
Finally, we print the In-order traversal of the tree to verify the inverted tree.
Let us have a look at the implementation:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
// import the Queue interface of Collections implemented using Linked List import java.util.Queue; import java.util.LinkedList; //Class for each node of tree class Node { int data; Node left, right; Node(int data) { this.data = data; left = null; right = null; } } class Tree { Node root; void invertTreeIterative(Node root) { if (root == null) return; Queue<Node> queue = new LinkedList<>(); //Add root first queue.add(root); //We do level order traversal while (queue.size() > 0) { // Get node of each level Node curr = queue.poll(); // swap left child with right child Node temp = curr.left; curr.left = curr.right; curr.right = temp;; // enqueue left and right child if (curr.left != null) queue.add(curr.left); if (curr.right != null) queue.add(curr.right); } } /* Helper function to test invertTree() by printing In-Order traversal*/ void printInOrder(Node node) { if (node == null) return; printInOrder(node.left); System.out.print(node.data + " "); printInOrder(node.right); } /*Driver code to test for sample tree*/ public static void main(String args[]) { /* creating a binary tree and entering the nodes */ Tree tree = new Tree(); tree.root = new Node(20); tree.root.left = new Node(10); tree.root.left.left = new Node(5); tree.root.left.right = new Node(15); tree.root.right = new Node(30); tree.root.right.left = new Node(25); tree.root.right.right = new Node(35); /* print inorder traversal of the input tree */ System.out.println("Inorder traversal of Input Tree is :"); tree.printInOrder(tree.root); System.out.println(); System.out.println(); /* convert tree to its mirror */ tree.invertTreeIterative(tree.root); /* Inorder traversal of the Inverted Binary tree */ System.out.println("Inorder traversal of Inverted Tree is : "); tree.printInOrder(tree.root); } } |
Output:
|
1 2 3 4 5 |
Inorder traversal of Input Tree is : 5 10 15 20 25 30 35 Inorder traversal of Inverted Tree is : 35 30 25 20 15 10 5 |
Time Complexity: It is same as recursive approach which require O(n) time as we traverse all nodes of tree.
Space Complexity: We use a Queue which stores all the nodes during execution so complexity is O(n).
That’s it for the article you can try and execute the above code. Feel free to ask your queries in the comment section.
