Binary Tree Right Side View

Tree BFS

Problem

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

For example:

Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

Thought Process

• The only additional thing we will be do is to append the last node of each level to the result array.

Solution

from collections import deque
class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        
        if not root:
            return []
        
        queue = deque()
        queue.append(root)
        res = []
        while queue:
            levelSize = len(queue)
            for i in range(0, levelSize):
                currentNode = queue.popleft()
                if i == levelSize-1:
                    res.append(currentNode.val)
                if currentNode.left:
                    queue.append(currentNode.left)
                if currentNode.right:
                    queue.append(currentNode.right)
        return res
        
#Time: O(n)
#Space: O(n)