Binary Tree Right Side View

Problem Summary

• Given a binary tree, return the right-side view of it

What is Being Asked?

• Get last item from each level using Level-order Traversal

Approach Taken

• At each level, append the last item from the level to the result

Why This Works

• When we do level order traversal, we just need to store the last item or the right-most item on the level

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Level-order Traversal
• Tree Traversal
• Trees
• Binary Tree

Time & Space Complexity

• Time: $O(n)$ → Reason: Processing each node
• Space: $O(b)$ → Reason: Breadth of the tree, could be $2^{h-1}$ where $h$ is height

Code

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

        queue = deque([root])
        result = [root.val]

        while queue:
            for _ in range(len(queue)):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            if queue:
                result.append(queue[-1].val)
        return result

Common Mistakes / Things I Got Stuck On

• Tried to run result.append(queue[-1].val) on an empty queue
• We need to check whether queue has an item or not because for the last iteration it will be empty otherwise we will never come out of the while loop