Holy Swift

Holy Swift

Merge Two Binary Trees In Swift

Merge Two Binary Trees In Swift

The Tree Love Algorithm

Subscribe to my newsletter and never miss my upcoming articles

Hoi vrienden, Leo hier.

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 the 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 for itself.

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

Let's code! But first....

The Painting

This is 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

You have two binary trees and you need to merge each value. For example: If the root node of first three is 1 and the root node of the second tree is 3 you have to merge into a root tree of value 4. If a leaf is 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 problem example image on Leetcode: Screenshot 2021-08-26 at 07.55.28.png

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

Simples isn't? Let's write it down:

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 tree to achieve this result.

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

Summary

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

That's all! I hope you liked as I enjoyed write this article. If you want to support this blog you can Buy Me a Coffee or just leave a comment saying hello. You can also sponsor posts and I'm open to writing freelancing! Just reach me in LinkedIn or Twitter for details.

Thanks for the reading and... That's all folks.

Credits: image

Interested in reading more such articles from Leonardo Maia Pugliese?

Support the author by donating an amount of your choice.

 
Share this