Problem

Given the root of 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.

Examples

Example 1:

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

Solution

Generally most of the problems are solved by DFS, but this is better solved with BFS. By better I mean easier.

Method 1 - Using Level Order Traversal

To capture the right view of a binary tree, a breadth-first traversal is used, but here we traverse each level from right to left. This approach ensures that the first node encountered at each level represents the rightmost node from that view.

Approach

  1. Initialization: Set two variables, currentLevel to 0 and nextLevel to 1.
  2. Right to Left Traversal: Begin traversing the tree from right to left at each level.
  3. Node Capture: Record the first node encountered at each level.
  4. Level Update: Update currentLevel to nextLevel when a new level is reached.
  5. Selective Node Printing: Print or capture the node only when currentLevel < nextLevel, ensuring only the first node of the new level is recorded.
  6. Continue and Compile: Repeat the process through all levels until the entire tree has been traversed and compile the results to form the right view.

Code

Java
class Solution {
    public List<Integer> rightView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();

            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();
                
                if (i == levelSize - 1) {
                    result.add(currentNode.val);
                }
                
                if (currentNode.left != null) {
                    queue.add(currentNode.left);
                }
                
                if (currentNode.right != null) {
                    queue.add(currentNode.right);
                }
            }
        }
        
        return result;
    }
}
Python
class Solution:
    def rightView(self, root: TreeNode) -> List[int]:
        result = []
        if not root:
            return result
        
        queue = deque([root])
        
        while queue:
            level_size = len(queue)
            
            for i in range(level_size):
                node = queue.popleft()
                
                if i == level_size - 1:
                    result.append(node.val)
                
                if node.left:
                    queue.append(node.left)
                
                if node.right:
                    queue.append(node.right)
        
        return result

Complexity

  • ⏰ Time complexity: O(n) - where n is the number of nodes in the binary tree. Each node is visited once.
  • 🧺 Space complexity: O(n) - due to the storage of nodes in the queue used for level order traversal.