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

--

--

--

 Software Developer, armanabkar@gmail.com

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

Recommended from Medium

Supporting iOS14 Approximate Location with Maps SDK v6.2.0

zoomed-out map of the Alexandria, Virginia region with a blue circle covering a large area

Flutter vs. Swift for better iOS development

TextField and UIViewRepresentable

LocalizedError Protocol in Swift

How I coded an iOS App in 20 minutes

Logging in Xamarin application: Building infrastructure with MvvmCross

Property Observers in Swift

9 Requirements for Setting up a new Xcode Project

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Arman Abkar

Arman Abkar

 Software Developer, armanabkar@gmail.com

More from Medium

Left Rotation HackerRank Swift Solution

Concurrency (Grand Central Dispatch) in Swift

Swift Programming: Structures / Enumerations / Switch statement

Making a testable singleton (with a lowercase s)