Invert Binary Tree easy

Problem Statement

Invert a binary tree.

Example:

Input:

 4

/
2 7 / \ /
1 3 6 9

Output:

 4

/
7 2 / \ /
9 6 3 1

Trivia: This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard.

Example 1

Input:

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

Output:

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

Example 2

Input:

   2
  / \
 1   3

Output:

   2
  / \
  3   1

Steps

1. Recursive Approach: We'll use a recursive function to traverse the tree.
2. Base Case: If the current node is nullptr (empty), we return nullptr.
3. Recursive Step: We recursively invert the left and right subtrees. Then, we swap the left and right children of the current node.

Explanation

The solution employs a recursive depth-first traversal of the binary tree. For each node encountered:

1. The left and right subtrees are recursively inverted. This ensures that the inversion process happens bottom-up, correctly handling all subtrees before swapping the children at the current level.
2. After the recursive calls return, the left and right children of the current node are swapped. This is the core operation of the inversion.

Code

/**
 * 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) {
        if (root == nullptr) {
            return nullptr; // Base case: empty subtree
        }

        // Recursively invert left and right subtrees
        TreeNode* leftInverted = invertTree(root->left);
        TreeNode* rightInverted = invertTree(root->right);

        // Swap left and right children
        root->left = rightInverted;
        root->right = leftInverted;

        return root;
    }
};

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node once.
• Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be equal to N. In the best case (a balanced tree), H is log₂(N).