DEV Community

Jaspreet singh
Jaspreet singh

Posted on

Right View of a Binary Tree

#algorithms #computerscience #interview #leetcode
leetcode.com

Problem Statement

Given the root of a binary tree, return the nodes visible when the tree is viewed from the right side.

Only the last node at each level is visible.

Brute Force Intuition

In an interview, you can explain it like this:

Perform a level-order traversal (BFS). For every level, record the last node encountered.

Since BFS already processes nodes level by level, identifying the last node is straightforward.

Complexity

  • Time Complexity: O(N)
  • Space Complexity: O(N)

Moving Towards the Optimal Approach

Notice that during BFS:

Each Level

↓

Processed Together
Enter fullscreen mode Exit fullscreen mode

If we know:

Level Size
Enter fullscreen mode Exit fullscreen mode

then the last node processed at that level is exactly the right view.

Pattern Recognition

Whenever you see:

  • Left View
  • Right View
  • Level Wise Traversal

Think:

Level Order Traversal (BFS)

Key Observation

For every level:

Last Node

↓

Right View
Enter fullscreen mode Exit fullscreen mode

Continue BFS until all levels are processed.

Optimal Approach

Step 1

Push the root into the queue.

Step 2

Process one level at a time.

size = queue.size();
Enter fullscreen mode Exit fullscreen mode

Step 3

The last node:

i == size - 1
Enter fullscreen mode Exit fullscreen mode

belongs to the right view.

Step 4

Push:

Left Child

↓

Right Child
Enter fullscreen mode Exit fullscreen mode

into the queue.

Optimal Java Solution 

class Solution {

    public List<Integer> rightSideView(TreeNode root) {

        List<Integer> ans = new ArrayList<>();

        if (root == null)
            return ans;

        Queue<TreeNode> q = new LinkedList<>();

        q.offer(root);

        while (!q.isEmpty()) {

            int size = q.size();

            for (int i = 0; i < size; i++) {

                TreeNode curr = q.poll();

                if (i == size - 1)
                    ans.add(curr.val);

                if (curr.left != null)
                    q.offer(curr.left);

                if (curr.right != null)
                    q.offer(curr.right);
            }
        }

        return ans;
    }
}
Enter fullscreen mode Exit fullscreen mode

Dry Run 

         1
       /   \
      2     3
     / \     \
    4   5     6
Enter fullscreen mode Exit fullscreen mode

Level 1 

1
Enter fullscreen mode Exit fullscreen mode

Last Node:

1
Enter fullscreen mode Exit fullscreen mode

Level 2 

2 3
Enter fullscreen mode Exit fullscreen mode

Last Node:

3
Enter fullscreen mode Exit fullscreen mode

Level 3 

4 5 6
Enter fullscreen mode Exit fullscreen mode

Last Node:

6
Enter fullscreen mode Exit fullscreen mode

Final Answer:

[1,3,6]
Enter fullscreen mode Exit fullscreen mode

Why BFS Works?

BFS processes nodes level by level.

Since nodes are visited from left to right, the last node processed at every level is exactly the node visible from the right side.

Complexity Analysis

Metric Complexity
Time Complexity O(N)
Space Complexity O(N)

Interview One-Liner

Perform a level-order traversal and record the last node encountered at every level.

Pattern Learned 

Level Order

↓

Last Node

↓

Right View
Enter fullscreen mode Exit fullscreen mode

Similar Problems

  • Right View of Binary Tree
  • Left View of Binary Tree
  • Top View
  • Bottom View
  • Zigzag Level Order Traversal

Memory Trick

Think:

One Level

↓

Last Node

↓

Answer
Enter fullscreen mode Exit fullscreen mode

Mental Model 

Queue

↓

Process One Level

↓

Pick Last Node

↓

Continue
Enter fullscreen mode Exit fullscreen mode

Whenever you hear:

"Right View of Binary Tree"

your brain should immediately think:

Level Order Traversal + Last Node of Every Level

Top comments (0)