Algorithm: Binary Tree Right Side View in Swift

Hallo vrienden, Leo hier. The Leetcode problem we will solve today is called Binary Tree Right Side View.

We will explore a binary tree problem. Binary tree problems usually are down to two main approaches, breadth-first search, and depth-first search, which are BFS and DFS respectively.

In our case, we will use BFS, because it fits perfectly in our problem. You can find and test it at Leetcode 199 problem.

No more talking let’s code… But first…

Painting of The Day

The paint I chose today is called Alleyway in the Park of Saint Cloud, a 1908 painting by Henri Rousseau. He was a French post-impressionist painter in a Naïve or Primitive manner. Also known as Le Douanier (the customs officer), a humorous description of his occupation as a toll and tax collector. Henri started painting seriously in his early forties; by age 49, he retired from his job to work on his art full-time.

Although the painting establishment laughed at and ridiculed his artistic style, he was highly regarded by artists who were outside the establishment, such as Picasso, Jean Hugo, Leger, Beckman, and later, painters of the Surrealist style. He was unaware that he was considered untrained by established painters and believed himself to be a great realist painter.

I chose that painting and the subtitle because we will do an exercise where we have to get only the right side of the tree, and that side is exactly the east, where the Sun rises.

The Problem – Binary Tree Right Side View

Given the root of a binary tree, imagine yourself standing on the right side of it, and return the values of the nodes you can see ordered from top to bottom.

The image below describes what we are going to achieve:

With the output: [1,3,4]

Notice that if after leaf 5 it has any nodes, the answer would have to contain it. So anything on the rightest side of the tree should be in the answer, independently of which branch it is.

The BFS technique we are going to use is slightly different from the most basic ones in this article.

Today we will have not only to queue all the elements but we also have to “consume” them before going to the next breadth level. We are going to do that by keeping track of the count of the nodes before starting a new breadth, that way keeping the order of everything.

Pseudo Algorithm

What we are going to do is:

1. Traverse with BFS the tree starts from the root node.
2. For each iteration, we will check if the current node is the rightmost element of that breadth. If the current node is the rightmost, we add to the answer.
3. Add the left node if exists to the queue.
4. Add the right node if exists to the queue.

Swift Solution

Let’s see how that looks in Swift. Check the solution below:

class Solution {
    
    var result = [Int]()
    func rightSideView(_ root: TreeNode?) -> [Int] {
        
        guard let root = root else { return [Int]() }
        
        var queue = [TreeNode]()
        
        queue.append(root)
        
        while !queue.isEmpty {
            let count = queue.count
            
            for x in 0..<count { // Mark 1
                
                let current = queue.removeFirst()
                
                if x == count - 1 { // Mark 2
                    result.append(current.val)
                }
                
                if let letfNode = current.left {
                    queue.append(letfNode)
                }
                
                if let rightNode = current.right {
                    queue.append(rightNode)
                }
                
            }
        }
        
        return result
    }
}

In Mark 1 you see the first part of this BFS variation. We use the count constant to traverse only the node of one breadth-level at a time.

For example, in the first iteration that will only be one node, we will only run the for loop one time, in the second iteration, we will have two nodes, that way we will run the for loop two times.

And for each iteration, we check if that element is the final element in Mark 2. That way we are sure that for any specific breadth of the tree we are picking up the rightmost element.

And we are done!

Summary – Binary Tree Right Side View in Swift

This is a really interesting algorithm because it involves a slightly different version of BFS and binary trees. Also, the visualization of this exercise is really interesting, for example, you could say that the Sun is on the right side of the tree.

This exercise is really interesting for people that want to learn a little more about BFS and binary trees.

That’s all my people, today we finished the Architecture and iOS Tooling article closing the series about the beginning of iOS development. 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