Inverting Binary Tree in Swift

LeetCode #226 challenge: Given a binary tree, write an algorithm to invert the tree and return its root

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

Example:

LeetCode, 226. Invert Binary Tree, Example 1

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

This challenge can be easily solved recursively. We need to write a method that inverts the given binary tree by swapping the left and right nodes and recursively performing the same process for each node until it reaches the leaf node. This will eventually transform the binary tree into its mirror image.

Here is the solution:

class Solution {
    func invertTree(_ root: TreeNode?) -> TreeNode? {
        guard let root = root else { return nil }
        (root.left, root.right) = (invertTree(root.right), 
                                   invertTree(root.left))
        return root
    }
}

1. When the binary tree is empty return nil; this is the base case to stop recursive calls when inverting is done.
2. For every node encountered, swap its left and right nodes and recursively perform the same process for each non-leaf node until it reaches the base case.

We used tuples to avoid creating temporary variables:

A tuple type is a comma-separated list of types, enclosed in parentheses. You can use a tuple type as the return type of a function to enable the function to return a single tuple containing multiple values.

Swift Official Documentation

Complexity Analysis

The time complexity of this solution is O(n) as each node is traversed only once. Since we have a Recursion, function calls are stored in a stack. The recursive function is called for every level and the worst-case is when the function calls of all levels are placed in the stack. Thus, if “h” is the height of the binary tree, the space complexity will be O(h).