Knowledge Guide
Home › DSA › Trees

medium Right View of a Binary Tree

Problem Statement

Given a root of the binary tree, return an array containing nodes in its right view.

The right view of a binary tree consists of nodes that are visible when the tree is viewed from the right side. For each level of the tree, the last node encountered in that level will be included in the right view.

Examples

Example 1

Image
Image

Example 2

Image
Image

Example 3

Image
Image

Constraints:

Try it yourself

Try solving this question here:

✅ Solution Right View of a Binary Tree

Problem Statement

Given a root of the binary tree, return an array containing nodes in its right view.

The right view of a binary tree consists of nodes that are visible when the tree is viewed from the right side. For each level of the tree, the last node encountered in that level will be included in the right view.

Examples

Example 1

  • Input: root = [1, 2, 3, 4, 5, 6, 7]
Image
Image
  • Expected Output: [1, 3, 7]
  • Justification:
    • The last node at level 0 is 1.
    • The last node at level 1 is 3.
    • The last node at level 2 is 7.

Example 2

  • Input: root = [12, 7, 1, null, 9, 10, 5, null, 3]
Image
Image
  • Expected Output: [12, 1, 5, 3]
  • Justification:
    • The last node at level 0 is 12.
    • The last node at level 1 is 1.
    • The last node at level 2 is 5.
    • The last node at level 3 is 3.

Example 3

  • Input: root = [8, 4, 9, 3, null, null, 10, 2]
Image
Image
  • Expected Output: [8, 9, 10, 2]
  • Justification:
    • The last node at level 0 is 8.
    • The last node at level 1 is 9.
    • The last node at level 2 is 10.
    • The last node at level 3 is 2.

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100

Solution

To solve this problem, we will use the Breadth-First Search (BFS) agorithm to traverse the binary tree and compute the right view of the tree. It processes the tree level by level, ensuring that at each level, the last node encountered (rightmost node) is stored in the result list. A queue is used to facilitate level-wise traversal, and at the end of each level, the last node is added to the result.

Step-by-Step Algorithm

  1. Base Case: If the root is null, return an empty list since there are no nodes to process.

  2. Initialize Queue: Create an empty queue and add the root node to it. This queue is used to traverse the tree level by level, starting from the root.

  3. While the Queue is Not Empty:

    • Determine Level Size: Calculate the number of nodes at the current level using queue.size(). This ensures that we process all nodes at the same level before moving to the next level.

    • Process Each Node at the Current Level:

      • For each node in the current level:
        • Dequeue the Current Node: Poll the node from the front of the queue.
        • Add its Left Child to the Queue: If the current node has a left child, add it to the queue to process in the next level.
        • Add its Right Child to the Queue: If the current node has a right child, add it to the queue for the next level.

    • Add the Last Node of the Level to the Result: After processing all nodes at the current level, add the value of the last node (rightmost node) to the result list. This node will represent the right view at that level.

  4. Repeat: Continue this process for each level until the queue is empty, meaning all levels have been processed.

  5. Return the Result: After processing all levels, the result list will contain the nodes visible from the right view of the tree.

Algorithm Walkthrough

Input: root = [12, 7, 1, null, 9, 10, 5, null, 3]

Image
Image

Step-by-Step Execution

  1. Initialization:

    • The root node is 12. Add 12 to the queue.

    Queue: [12] Result: []

  2. Level 1:

    • queue.size() is 1, meaning there is 1 node at this level.
    • Dequeue node 12.
    • Add its left child (7) and right child (1) to the queue.
    • Add 12 in the result list.

    Queue: [7, 1] Result: [12]

  3. Level 2:

    • queue.size() is 2, meaning there are 2 nodes at this level.
    • Dequeue node 7. Add its right child (9) to the queue (it has no left child).
    • Dequeue node 1. Add its left child (10) and right child (5) to the queue.
    • Since 1 is the last node at this level, add it to the result.

    Queue: [9, 10, 5] Result: [12, 1]

  4. Level 3:

    • queue.size() is 3, meaning there are 3 nodes at this level.
    • Dequeue node 9. Add its right child (3) to the queue (it has no left child).
    • Dequeue node 10. It has no children.
    • Dequeue node 5. It has no children.
    • Since 5 is the last node at this level, add it to the result.

    Queue: [3] Result: [12, 1, 5]

  5. Level 4:

    • queue.size() is 1, meaning there is 1 node at this level.
    • Dequeue node 3. Since it's the only node at this level, add it to the result.
    • Node 3 has no children, so nothing is added to the queue.

    Queue: [] Result: [12, 1, 5, 3]

  6. Completion: The queue is now empty, meaning all levels of the tree have been processed. The right view of the tree is complete.

Final Output: [12, 1, 5, 3]

Code

Here is the code for this algorithm:

java
import java.util.*;

// class TreeNode {
//   int val;
//   TreeNode left;
//   TreeNode right;

//   TreeNode(int x) {
//     val = x;
//   }
// };

class Solution {

  public List<Integer> traverse(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
      int levelSize = queue.size();
      TreeNode currentNode = null;
      for (int i = 0; i < levelSize; i++) {
        currentNode = queue.poll();
        // insert the children of current node in the queue
        if (currentNode.left != null) queue.offer(currentNode.left);
        if (currentNode.right != null) queue.offer(currentNode.right);
      }
      // Add last node of the current node in the result.
      result.add(currentNode.val);
    }

    return result;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    TreeNode root = new TreeNode(12);
    root.left = new TreeNode(7);
    root.right = new TreeNode(1);
    root.left.left = new TreeNode(9);
    root.right.left = new TreeNode(10);
    root.right.right = new TreeNode(5);
    root.left.left.left = new TreeNode(3);
    List<Integer> result = sol.traverse(root);
    for (Integer nodeVal : result) {
      System.out.print(nodeVal + " ");
    }
  }
}

Time Complexity

The time complexity of the above algorithm is , where ‘N’ is the total number of nodes in the tree. This is due to the fact that we traverse each node once.

Space Complexity

  • The space complexity of the above algorithm will be for the queue. Since we can have a maximum of N/2 nodes at any level (this could happen only at the lowest level), therefore we will need space to store them in the queue.
  • Also, we use space space for result list. For the skewed tree we need to store all N elements in the result list.

Similar Questions

Problem 1: Given a binary tree, return an array containing nodes in its left view. The left view of a binary tree is the set of nodes visible when the tree is seen from the left side.

Solution: We will be following a similar approach, but instead of appending the last element of each level, we will be appending the first element of each level to the output array.

🤖 Don't fully get this? Learn it with Claude

Stuck on Right View of a Binary Tree? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Right View of a Binary Tree** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Right View of a Binary Tree** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Right View of a Binary Tree**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Right View of a Binary Tree**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Deepest Leaves SumKth Smallest Element in a BST →