Search⌘ K
Home
Courses
Decode the Coding Interview in Java: Real-World Examples

Invert Binary Tree

Explore how to invert a binary tree using depth-first search in this lesson. Understand the step-by-step process to swap left and right subtrees recursively, and analyze the time and space complexities involved. This lesson helps you solidify your grasp of tree manipulation and recursion, key skills for coding interviews involving tree data structures.

We'll cover the following...

Description

In this lesson, your task is to invert a given a binary tree, T.

Let’s look at an example below:

Java
class Solution {
    public static TreeNode invertTree(TreeNode root) {
        return root;
    }
}
Invert binary tree

Solution

We can solve this problem using depth-first search (DFS).

The inverse of an empty tree is the empty tree. To invert tree T with root and subtrees left and right, we keep root the same and invert the right and left subtrees.

Let’s review the implementation below:

Java
class Solution {
    public static TreeNode invertTree(TreeNode root) {
        if (root == null) {
        return root;
    }
        TreeNode right = invertTree(root.right);
        TreeNode left = invertTree(root.left);
        root.left = right;
        root.right = left;
        return root;
    }
    public static void main(String args[]){
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        Utility.print(invertTree(root));
    }
}
Invert binary tree

Complexity measures

Time Complexity Space Complexity
...