Invert Binary Tree

LeetCode Problem #226 (Easy)

Problem Statement

Invert a binary tree.

Testcase

Input:
         4
       /   \
      2     7
     / \   / \
    1   3 6   9
    
Output:
         4
       /   \
      7     2
     / \   / \
    9   6 3   1

Prerequisite Knowledge

Binary Tree

A binary tree is a tree data structure in which each parent node has a maximum of two child nodes.

Binary Tree

Level Order Traversal

Level Order Tree Traversal is also known as Breadth-First Traversal. In this type of traversal, we traverse through and print the nodes at each level before traversing further down the tree, as shown in the example.

Level Order Traversal: 1->2->3->4->5

Problem Explanation

Inverting a Binary Tree

An inverted binary tree is a mirror image of the original binary tree. At every level of the binary tree, we must swap the left and right nodes in order to obtain an inverted image of the binary tree.

Original Tree vs. Inverted Tree

Algorithm

Recursive Approach

1. If the tree is empty, return NULL as the inverse of an empty tree is an empty tree.

2. Recursively traverse through the left and right branches of the tree in a depth-first manner.

3. When the leaf nodes have been reached, set the respective left and right pointers to NULL.

4. Backtrack through each level and swap the left and right sub-trees.

5. The process is completed when the root node is reached.

Time Complexity: O(n)

Code

TreeNode* invertTree(TreeNode* root) {
    // Inverse of an empty tree is an empty tree
    if (root == NULL) {
        return NULL;
    }
        
    // Recursively invert each subtree starting from the root
    TreeNode *right = invertTree(root->right);
    TreeNode *left = invertTree(root->left);
            
    // Exchange the pointers to the left and right nodes
    root->left = right;
    root->right = left;
        
    return root;
}