algoadvance

Leetcode 226. Invert Binary Tree

Problem Statement

Leetcode Problem 226: Invert Binary Tree

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

For example, if the input binary tree is:

     4
   /   \
  2     7
 / \   / \
1   3 6   9

The inverted binary tree is:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Clarifying Questions

  1. Input Specifications: Will the tree be given as TreeNode objects or a different format?
    • Tree is provided as TreeNode objects.
  2. Constraints:
    • What is the expected size of the binary tree (in terms of number of nodes)?
      • The number of nodes in the tree is in the range [0, 100].
    • Can the binary tree have negative values?
      • Yes, the tree nodes can have negative values.
  3. Edge Cases:
    • What should be returned if the root is null?
      • If the root is null, the function should return null.

Strategy

To invert a binary tree, we need to swap the left and right children at each node. We can achieve this using either recursion or iteration.

Recursive Approach

  1. Base Case: If the current node is null, return null.
  2. Recursive Step:
    • Swap the left child and the right child.
    • Recursively invert the left and right subtree.

Iterative Approach

  1. Using a Queue (BFS): Use a queue to traverse the tree level by level and swap children iteratively.
    • Initialize the queue with the root node.
    • While the queue is not empty:
      • Dequeue a node.
      • Swap its children.
      • Enqueue the non-null children.

We will use the recursive approach in this solution because it is more intuitive and simpler to implement for binary tree problems.

Time Complexity

The time complexity for both the recursive and iterative approaches is O(n), where n is the number of nodes in the binary tree. Each node is visited once, and a constant amount of work is done per node.

Code

Here’s the implementation of the recursive approach in C++:

#include <iostream>

// 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 tree is empty, return null
        if (root == nullptr) {
            return nullptr;
        }
        
        // Swap the left and right children of the current node
        TreeNode* temp = root->left;
        root->left = root->right;
        root->right = temp;
        
        // Recursively invert the left subtree and right subtree
        invertTree(root->left);
        invertTree(root->right);
        
        return root;
    }
};

// Usage example
int main() {
    TreeNode* root = new TreeNode(4);
    root->left = new TreeNode(2);
    root->right = new TreeNode(7);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(3);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(9);
    
    Solution sol;
    TreeNode* invertedRoot = sol.invertTree(root);
    
    // Output the result (for testing purposes)
    // Expected output should show the structure of the inverted tree
    std::cout << "Root: " << invertedRoot->val << std::endl;
    std::cout << "Left child: " << invertedRoot->left->val << std::endl;
    std::cout << "Right child: " << invertedRoot->right->val << std::endl;

    return 0;
}

This solution will correctly invert a binary tree using a recursive approach. The main function shows how to use the invertTree function and print the results for testing purposes.

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