Inverting a binary tree or mirroring a binary tree is a common interview question. We will solve LeetCode “226. Invert Binary Tree” problem here. The problem statement is as follows:
Given the root of a binary tree, invert the tree, and return its root.
Input: [1, 2, 3, 4, 5, 6, 7] Output: [1, 3, 2, 7, 6, 5, 4]
The solution should be straightforward. As we can see from the diagram above, left child in original tree becomes right child in inverted tree. And right child in original tree becomes left child in inverted tree. So we can start from root node and swap left & right children of root node. Then we would have to do this same process recursively for left subtree & right subtree till we reach the leaf nodes. In the java solution below, we have used a modified pre-order traversal of binary tree to achieve the same. Code is pretty simple & should be easy to understand.
Time complexity of the solution is O(n) because we traverse every node once.
The maximum size of recursion tree is O(h) where h is the height of the binary tree. We are doing a depth-first traversal. So once recursion level reaches h, it will only come down & go back to the previous level. At each recursion level, we are using one temporary local variable to do the swapping of left & right children of current node. So at each recursion level, space utilization is constant or O(1). So overall space complexity after considering recursion tree is O(h).
Here is the fully working Java code solution to mirror a binary tree or invert a binary tree. It has been validated in LeetCode.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode A) {
TreeNode curr = A;
if(curr != null){
TreeNode temp = curr.left;
curr.left = curr.right;
curr.right = temp;
invertTree(curr.left);
invertTree(curr.right);
}
return curr;
}
}