Problem Statement: Given root of a binary tree,invert the binary tree and return its root.
Inverting a binary tree means to interchange the children of current node i.e make the left child right and right child left.
Example 1:
Input: root = [5,2,3,4,6,7,8]
Output: 5 3 2 8 7 6 4
Output: 5 3 2 8 7 6 4
Approach:
In order to invert a binary tree, we need to change the left and right pointer of current node by interchanging the child nodes and similarly go on recursively to solve the subtrees also.
Code Implementation:
import java.util.LinkedList;
import java.util.Queue;
public class InvertTree {
public static class Node {
int val;
Node left, right;
// Constructor
Node(int val) {
this.val = val;
left = right = null;
}
}
/* method which inverts the tree */
private static Node invertTree(Node root) {
if (root == null)
return root;
Node left = invertTree(root.left);
Node right = invertTree(root.right);
root.left = right; // changing the links of root, pointing left of root to right child
root.right = left; // pointing right of root to left child
return root;
}
public static void main(String[] args) {
/*
* Creating Binary Tree The created binary tree is same as in the above given
* figure (refer figure for reference)
*/
Node root = new Node(5);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(6);
root.right.left = new Node(7);
root.right.right = new Node(8);
/* calling invertTree method */
invertTree(root);
printLevelOrder(root); // printing the inverted tree
}
private static void printLevelOrder(Node root) {
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (queue.size() != 0) {
int size = queue.size();
for (int i = 0; i < size; i++) {
Node temp = queue.poll();
/* printing the values of merged tree */
System.out.print(temp.val + " ");
if (temp.left != null) {
queue.add(temp.left);
}
if (temp.right != null) {
queue.add(temp.right);
}
}
}
}
}
Output:
5 3 2 8 7 6 4
Complexity Analysis:
Time Complexity: O(n), where n is the number of nodes in tree.
Space Complexity: Considering the stack space, the space complexity is equal to height of tre i.e O(h).
If you want to contribute such articles to solutions2coding.com please click here. Thank you!