Problem Statement in English

You’re given a binary tree. Your task is to return a list of all nodes that can be seen from the right side.

Approach

Fundamentally, this is just a list of the rightmost nodes in each level. That’s it.

So all we’re going to do, is go over this tree level by level, and add the rightmost node to our answer.

Essentially, we apply a Breadth First Search.

Solution in Python


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []

        # the main queue
        q1 = [root]
        # the queue of all children of nodes in `q1`
        q2 = []

        # this contains our answer
        ans = []

        # operate while `q1` is not empty
        while q1:
            # go over each node in `q1`
            for i in range(len(q1)):
                node = q1[i]
                # if the current node has a left child
                if node.left:
                    # add it to `q2`
                    q2.append(node.left)
                # if the current ndoe has a right child
                if node.right:
                    # add it to `q2`
                    q2.append(node.right)
                # if this is the last node in `q1`, then it's visible from the right side
                if i == len(q1) - 1:
                    # so add it to `ans`
                    ans.append(q1[i].val)
            # set q1 to be q2
            q1 = q2
            # empty q2
            q2 = []

        return ans

Complexity

  • Time: O(n)O(n)
    Since we traverse nn nodes.

  • Space: O(n)O(n)
    We store at most, nn elements in our queue.

And we are done.