Invert Binary Tree

EASY

Description

Given the root of a binary tree, invert the tree, and return its root.

Example 1:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Example 2:

Input: root = [2,1,3]
Output: [2,3,1]

Example 3:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

Approaches

Checkout 2 different approaches to solve Invert Binary Tree. Click on different approaches to view the approach and algorithm in detail.

Recursive Approach

We can solve this problem using a recursive approach where we swap the left and right children of each node recursively.

Algorithm

Check if root is null, return null if true
Store left child in temporary variable
Assign right child to left child
Assign temporary variable (original left child) to right child
Recursively call invertTree on left child
Recursively call invertTree on right child
Return root

The recursive approach works by traversing the binary tree and swapping the left and right children of each node. For each node:

First check if the root is null, if yes return null
Swap the left and right children of the current node
Recursively invert the left subtree
Recursively invert the right subtree
Return the root node

Here's the implementation:

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 root) {
        // Base case: if root is null, return null
        if (root == null) {
            return null;
        }
        
        // Swap the left and right children
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        
        // Recursively invert left and right subtrees
        invertTree(root.left);
        invertTree(root.right);
        
        return root;
    }
}

Complexity Analysis

Time Complexity: O(n) where n is the number of nodes in the tree as we need to visit each node onceSpace Complexity: O(h) where h is the height of the tree due to the recursive call stack. In worst case (skewed tree) it can be O(n)

Pros and Cons

Pros:

Simple and easy to understand
Clean and concise code
Uses less space compared to iterative approach

Cons:

Can cause stack overflow for very deep trees
Recursive calls may have overhead

Code Solutions

Checking out 5 solutions in different languages for Invert Binary Tree. Click on different languages to view the code.

/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { public TreeNode InvertTree ( TreeNode root ) { if ( root == null ) { return null ; } TreeNode l = InvertTree ( root . left ); TreeNode r = InvertTree ( root . right ); root . left = r ; root . right = l ; return root ; } }

Video Solution

Watch the video walkthrough for Invert Binary Tree

Algorithms:

Depth-First SearchBreadth-First Search

Data Structures:

TreeBinary Tree

Companies:

Oracle |Ozon |