Leetcode 199. Binary Tree Right Side View

Problem

Leetcode 199 - Binary Tree Right Side View

Example:

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

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

Input: root = [1,null,3]
Output: [1,3]

Input: root = []
Output: []

Approach

We can use BFS and read all the nodes from left to right. Once for loop on that level is over, our current is going to be the right most at that level. Thus, we can add that node/node’s value in to result.

Here is the Python code for the solution:

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

        q = deque()
        q.append(root)
        res = []

        while q:
            for _ in range(len(q)):
                curr = q.popleft()
                if curr.left:
                    q.append(curr.left)
                if curr.right:
                    q.append(curr.right)
            res.append(curr.val)
        
        return curr    

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(n)$