Binary Tree Right Side View - Video Solutions

Problem Overview: Given the root of a binary tree, return the values of the nodes you would see when looking at the tree from the right side. For each depth level, only the rightmost node should appear in the result.

Approach 1: Breadth-First Search (Level Order) using Queue (Time: O(n), Space: O(w))

This approach performs a level order traversal using a queue. You process the tree level by level, pushing the left and right children of each node into the queue. The key observation: the last node processed at each level represents the node visible from the right side. Track the queue size at the start of each level, iterate through that many nodes, and record the value of the final node. This method is intuitive because it directly models the level structure of a binary tree. Space complexity depends on the maximum width w of the tree, since the queue stores nodes from a level.

Approach 2: Depth-First Search (Right-First Traversal) (Time: O(n), Space: O(h))

This solution uses recursion and explores the right subtree before the left subtree. Maintain a result list where the index corresponds to the tree depth. When visiting a node, check if the current depth equals the size of the result list. If it does, this is the first node seen at that depth, which must be the rightmost one because the traversal prioritizes the right side. Append its value. Then recursively visit the right child followed by the left child. This pattern leverages Depth-First Search to ensure the rightmost node is encountered first at each level. The recursion stack requires O(h) space where h is the tree height.

Both approaches traverse every node exactly once, giving O(n) time complexity. The difference lies in traversal style: BFS processes nodes level by level using a queue, while DFS uses recursion and depth tracking.

Recommended for interviews: The BFS level-order solution is the most commonly expected answer because it directly maps to the concept of "last node per level" and clearly demonstrates understanding of Breadth-First Search. The DFS right-first approach is equally optimal and often impresses interviewers because it shows deeper control over traversal order and recursion depth.