Java Program to Invert the Binary Tree

Inverting a binary tree is common interview question.

Input:
     1
/
2 3
/ /
4 5 6 7
Output:
    1
/
3 2
/ /
7 6 5 4
We can use recursion to swap left & right sub-trees. Time complexity would be O(n) as we will be doing a full traversal of the binary tree. You can find the Java solution below:

 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
import java.util.*;
import java.lang.*;
import java.io.*;

//Definition for binary tree
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
left=null;
right=null;
}
}

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

Leave a Comment