# 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:

`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).

--

--

--

## More from Arman Abkar

 Software Developer, armanabkar@gmail.com

Love podcasts or audiobooks? Learn on the go with our new app.

## Arman Abkar

 Software Developer, armanabkar@gmail.com