Leetcode 226: Invert Binary Tree

Input: The input is the root of a binary tree, where each node contains an integer value and references to its left and right children.

Example: Input: root = [3,1,4,null,2,null,5]

Constraints:

• The number of nodes in the tree is in the range [0, 100].

• -100 <= Node.val <= 100

Output: The output is the root of the inverted binary tree, where the left and right subtrees of every node are swapped.

Example: Output: [3,4,1,5,null,null,2]

Constraints:

• The structure of the tree must maintain binary tree properties during inversion.

Goal: Swap the left and right subtrees recursively for every node in the binary tree.

Steps:

• Base Case: If the current node is null, return null.

• Recursively invert the left subtree.

• Recursively invert the right subtree.

• Swap the left and right children of the current node.

• Return the root node.

Goal: The problem is subject to the following constraints:

Steps:

• The binary tree can contain up to 100 nodes.

• Each node value is an integer in the range [-100, 100].

Assumptions:

• The input tree is well-formed and adheres to binary tree properties.

• Node values can include negative integers.

• Input: Input: root = [5,3,8,1,4,7,9]

• Explanation: The tree is inverted by swapping the left and right children of each node. Output: [5,8,3,9,7,4,1]

• Input: Input: root = []

• Explanation: An empty tree remains empty after inversion. Output: []

Approach: The approach uses a recursive algorithm to traverse the binary tree and swap the left and right subtrees of every node.

Observations:

• Inverting a tree requires swapping child nodes at each level.

• A depth-first traversal is suitable for recursive inversion.

• Recursion is a natural fit for this problem as it aligns with the tree structure.

• Handling the base case (null nodes) ensures no invalid accesses occur.

Steps:

• Check if the current node is null. If so, return null.

• Recursively call the inversion function on the left subtree.

• Recursively call the inversion function on the right subtree.

• Swap the left and right child references of the current node.

• Return the current node.

Empty Inputs:

• An input tree with no nodes.

Large Inputs:

• A complete binary tree with 100 nodes.

Special Values:

• A tree where all nodes have the same value.

• A tree with only left or right subtrees.

Constraints:

• Ensure the function works with nodes containing the minimum and maximum possible values.

TreeNode* invertTree(TreeNode* root) {
    if(!root) return NULL;
    TreeNode* tmp = root->left;
    root->left = invertTree(root->right);
    root->right = invertTree(tmp);
    return root;
}

1 : Function Definition

TreeNode* invertTree(TreeNode* root) {

Defines the `invertTree` function, which takes the root of a binary tree and returns the root of the inverted tree.

2 : Base Case

    if(!root) return NULL;

Checks if the root is NULL (base case for recursion). If it is NULL, the function returns NULL, ending the recursion.

3 : Temporary Variable

    TreeNode* tmp = root->left;

Stores the left child of the current node in a temporary variable `tmp` to facilitate swapping the left and right children.

4 : Recursive Call 1

    root->left = invertTree(root->right);

Recursively inverts the right subtree of the current node and assigns it to the left child of the current node.

5 : Recursive Call 2

    root->right = invertTree(tmp);

Recursively inverts the left subtree (stored in `tmp`) and assigns it to the right child of the current node.

6 : Return Inverted Tree

    return root;

Returns the root node of the inverted tree.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: Each node is visited exactly once during the inversion process.

Best Case: O(1)

Worst Case: O(h)

Description: The space complexity is determined by the recursion stack, which is O(h), where h is the height of the tree.

Leetcode 226: Invert Binary Tree

Solution to LeetCode 226: Invert Binary Tree Problem

Explore →