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

Comments