Keyboard shortcuts

Press or to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Invert Binary Tree 🧠

LeetCode Link: Invert Binary Tree

Difficulty: Easy

Problem Explanation 📝

Problem: LeetCode 226 - Invert Binary Tree

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

Intuition: To invert a binary tree, we need to swap the left and right subtrees of each node. This can be done recursively, starting from the root node and swapping the children of each node.

Approach:

  1. Implement a recursive function to invert the binary tree.
  2. If the root is null, return null.
  3. Swap the left and right children of the root node.
  4. Recursively invert the left and right subtrees.
  5. Return the modified root.

Time Complexity: The time complexity of the approach is O(n), where n is the number of nodes in the binary tree. We visit each node once.

💾 Space Complexity: The space complexity is O(h), where h is the height of the binary tree. This is the space used by the recursive call stack.

Solutions 💡

Cpp 💻

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
  public:
    TreeNode *invertTree(TreeNode *root) {
        // Base case: if the root is null, return null
        if (root == nullptr) {
            return nullptr;
        }

        // Swap the left and right children of the root node
        swap(root->left, root->right);
        // Recursively invert the left and right subtrees
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

Python 🐍

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right


class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None

        # Swap left and right subtrees
        root.left, root.right = root.right, root.left

        # Recursively invert left and right subtrees
        self.invertTree(root.left)
        self.invertTree(root.right)

        return root