algoadvance

Leetcode 226. Invert Binary Tree

Problem Statement

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

Example:

Input: Root of the Binary Tree
Output: Root of the Inverted Binary Tree

Clarifying Questions

1. Can the input tree be empty?
   • Yes, the input can be an empty tree (root is null).
2. Can the tree have only one node?
   • Yes, the tree can have a single node.
3. Is there any constraint on the size of the tree?
   • There are no explicit constraints, but typical constraints for binary tree problems on LeetCode are applicable.
4. Is there a specific order in which we need to traverse the tree to invert it?
   • No specific order is required as long as the final tree is inverted.

Strategy

Steps:

1. Base Case: If the tree is empty (root is null), return null.
2. Recursive Case:
   • Invert the left subtree.
   • Invert the right subtree.
   • Swap the left and right subtrees.
3. Return the current root of the tree after inversion.

Approach:

We can use recursion to invert the binary tree. The function will recursively invert the left and right subtrees and then swap them.

Code:

/**
 * 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 root) {
        // Base case: if the tree is empty, return null
        if (root == null) {
            return null;
        }

        // Recursively invert the left and right subtrees
        TreeNode leftInverted = invertTree(root.left);
        TreeNode rightInverted = invertTree(root.right);

        // Swap the left and right children
        root.left = rightInverted;
        root.right = leftInverted;

        // Return the current root
        return root;
    }
}

Time Complexity

• Time Complexity: O(n), where n is the number of nodes in the binary tree. Each node is visited exactly once.
• Space Complexity: O(h), where h is the height of the tree. This represents the stack space utilized by the recursive function calls. In the worst case (unbalanced tree), it can grow to O(n).

This recursive approach ensures that each node is visited and its left and right children are swapped, resulting in the inversion of the binary tree.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?