Invert Binary Tree

Problem Statement

LeetCode-226: Given the root of a binary tree, invert the tree, and return its root.

Approach

As clear from the problem statement, and the illustration tagged above, we need to swap the left and right subtrees of every node from root till leaf nodes.

As we need to work on every single level from bottom up, this seem to be a clear candidate of a recursive solution. The base case(s) for the same being the following two scenarios:

1. Empty tree - no inversion required.
2. Leaf Node - no inversion required.

For every other scenario, get a reference to the left and right subtrees and swap those for current node.

Implementation

Following is a java based recursive approach to solve this problem:

public TreeNode invertTree(TreeNode root) {
    // base condition if empty tree or leaf nodes
    // return as no inversion is required
    if(null == root || (null == root.left && null == root.right)){
        return root;
    }

    // recursively find left and right
    // subtrees in a bottom up fashion
    TreeNode left = invertTree(root.left);
    TreeNode right = invertTree(root.right);
    
    // swap the nodes
    root.left = right;
    root.right = left;
    
    // return current node
    return root;
}

Complexity Analysis

As we are visiting every single node once, the overall runtime complexity of the algorithm is \(O(n)\).