Hoi vrienden, Leo hier. The topic today is how to merge two binary trees in Swift and why you should learn that amazing algorithm.

Today we will solve this algorithm question that uses binary trees and recursion to achieve a really nice solution. Trees algorithms usually use recursion because it’s easier to reason about it, and a code easy to read is very important when we talk about algorithms because is a complex subject in itself.

This kind of post is very niche but is a subject that I like. If you have any algorithm problem that you want to be solved in Swift, just leave a comment below!

Let’s code! But first…

Painting of The Day

This is a painting called Tree of Life painted by Elisa S. It is an acrylic painting on canvas, the size is 100/70 cm, representing two trees hugging and growing together they have strong grounded roots and they grow big and strong together, the tree of life is a symbol and in itself, it symbolises also the striving for growth, health love all in one, the grow big and strong together.

I choose that because the white and the brown trees are merging together. Such a lovely scene, isn’t it?

The Problem – Merge Two Binary Trees In Swift

> You have two binary trees and you need to merge each value. For example: If the root node of the first three is 1 and the root node of the second tree is 3 you have to merge into a rooted tree of value 4. If a leaf is a nil you just use the value of the other tree for the same position.

The problem is best described here in Leetcode. There you can test your solution.

This is a problem example image on Leetcode:

First of all, open your favorite playground and copy this TreeNode class to it:

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init() { self.val = 0; self.left = nil; self.right = nil; }
    init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

We don’t have too much to explain here. This is a class, it could be implemented as a `enum` but that implementation is for another post, holding three variable properties: the value as an Int, the left and right as a TreeNode.

The algorithm steps are pretty straightforward. Just remember that every time you write down a recursive algorithm the first thing in mind is the escape clause. The steps to solve this problem are easy:

1. First escape clause is if root1 is nil, just return root2
2. Second escape clause is if root2 is nil, just return root1
3. Now you know none of the roots are nil, you can sum both root values.
4. Start the recursive process overriding the left node with the result of the mergeTrees with the left node of both roots.
5. When the left node recursion finishes you can do the same process to the right node.
6. Return the merged root1

Simple isn’t it?

Solving the problem

Now let’s code it:

class Solution {
    func mergeTrees(_ root1: TreeNode?, _ root2: TreeNode?) -> TreeNode? {
        guard let root1 = root1 else { // Step 1
            return root2
        }
        guard let root2 = root2 else { // Step 2
            return root1
        }
        
        root1.val += root2.val // Step 3
        
        root1.left = mergeTrees(root1.left, root2.left) // Step 4
        root1.right = mergeTrees(root1.right, root2.right) // Step 5
        
        return root1 // Step 6
    }
}

One interesting part of this algorithm is that the escape clause is a shortcut too. Imagine that you have a big branch of left nodes from root1, but just a nil value for the left branch of root2. With the escape clause, you merge all the left nodes from the `root1` and you don’t need to traverse all trees to achieve this result.

Now you can easily merge binary trees in Swift. Very cool right?

Continue Studying Algorithms

If there’s a classic algorithmic problem in computer science, for sure is the legendary “Reverse a Linked List”. Luck that we have means to study that in Swift, and not only one answer, but you also have at least two ways to do that in Swift.

You can do it iteratively as I show in this article. Or if you prefer a more sophisticated one, you can do it recursively as this article shows.

Either way, you are good to go on an interview situation.

Summary – Merge Two Binary Trees In Swift

Today we explore a way to merge two binary trees into one. It’s a very simple but elegant algorithm to solve this classic problem.

That’s all my people, I hope you liked reading this article as much as I enjoyed writing it. If you want to support this blog you can Buy Me a Coffee or leave a comment saying hello. You can also sponsor posts and I’m open to freelance writing! You can reach me on LinkedIn or Twitter and send me an e-mail through the contact page.

Thanks for reading and… That’s all folks.

Credits:

title image