Right View of a Binary Tree - Iterative Approach

Problem Statement❯

Given a binary tree, return the right view of the tree using an iterative level-order traversal approach. The right view of a binary tree includes the last node at each level when the tree is viewed from the right side.

Examples❯

Input Tree	Right View Output	Description
[1, 2, 3, 4, 5, null, 6]	[1, 3, 6]	Standard case: Nodes visible from the right at each level
[1]	[1]	Single-node tree: root is the only visible node
[]	[]	Empty tree: no nodes to view from any side
[1, 2, null, 3, null, null, null, 4]	[1, 2, 3, 4]	Left-skewed tree: right view includes one node per level
[1, null, 2, null, null, null, 3]	[1, 2, 3]	Right-skewed tree: all nodes are visible in the right view
[10, 20, 30, null, 25, null, 35]	[10, 30, 35]	Balanced tree with both left and right children

Visualization Player

Solution❯

Understanding the Problem

The Right View of a Binary Tree refers to the set of nodes visible when the tree is viewed from the right side. At each level of the tree, we only see the rightmost node. Our task is to return a list of such nodes, ordered from top to bottom.

To solve this, we need to understand how trees are structured and how to explore them level by level. We will use a level-order traversal approach (like BFS), and for each level, we will record the last node encountered—this node represents what we see from the right side at that level.

Step-by-Step Solution with Example

Step 1: Understand the input format

The binary tree is typically represented as a level-order list like [1, 2, 3, null, 5, null, 4]. Each element corresponds to a node in the tree, and null indicates a missing child.

Step 2: Perform level-order traversal

We use a queue to explore the tree level by level. For each level, we loop through all nodes, and we keep track of the last node encountered in that level—this is the one visible from the right side.

Step 3: Apply the logic on the example

Let’s consider the tree represented by [1, 2, 3, null, 5, null, 4]. This corresponds to:

    1
   /   2   3
           5    4

Now we traverse level by level:

Level 1: Nodes = [1] → Rightmost = 1
Level 2: Nodes = [2, 3] → Rightmost = 3
Level 3: Nodes = [5, 4] → Rightmost = 4

So the final right view is [1, 3, 4].

Step 4: Store the result

As we detect the rightmost node at each level, we append it to a result list. After processing all levels, we return this list as our right view.

Edge Cases

Case 1: Tree is empty

If the binary tree has no nodes, then there is nothing to view. The right view is simply an empty list: [].

Case 2: Tree has only one node

When the tree contains just a single root node, that node is by default the right view. Example: [1] → Right view: [1].

Case 3: Tree is right skewed

If every node has only a right child, the entire tree is visible from the right. Example: [1, null, 2, null, 3] → Right view: [1, 2, 3].

Case 4: Tree is left skewed

Even though the nodes are on the left, each level has only one node, making it the rightmost by default. Example: [1, 2, null, 3] → Right view: [1, 2, 3].

Case 5: Tree has both left and right children

This is the general case where our logic must correctly select the last node from each level during traversal. The method we implemented ensures this behavior.

Finally

The key idea is to visit the tree level by level and pick the last node at each level. This last node is what you would see from the right. By using a queue and simple bookkeeping, we can ensure the solution works for skewed trees, balanced trees, and even empty trees.

This problem is a great introduction to BFS traversal and thinking about trees from different perspectives. Once you understand level-order traversal, the rest of the solution becomes very intuitive!

Algorithm Steps❯

Given a binary tree, if the tree is empty, return an empty result.
Initialize a queue and enqueue the root node.
While the queue is not empty, determine the number of nodes at the current level (levelSize).
For each node in the current level, dequeue a node.
If the node is the last one in the level (i.e. for index i == levelSize - 1), record its value as part of the right view.
Enqueue the left and then right child of the node (if they exist) for processing in the next level.
Repeat until all levels are processed; the recorded values form the right view of the binary tree.

Code

C++

Python

Java

Rust

Kotlin

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

int* rightSideView(TreeNode* root, int* returnSize) {
    if (!root) {
        *returnSize = 0;
        return NULL;
    }
    int* result = malloc(100 * sizeof(int));
    TreeNode** queue = malloc(100 * sizeof(TreeNode*));
    int front = 0, rear = 0, resIndex = 0;
    queue[rear++] = root;
    while (front < rear) {
        int levelSize = rear - front;
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = queue[front++];
            if (i == levelSize - 1)
                result[resIndex++] = node->val;
            if (node->left) queue[rear++] = node->left;
            if (node->right) queue[rear++] = node->right;
        }
    }
    *returnSize = resIndex;
    free(queue);
    return result;
}

int main() {
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->right = createNode(5);
    root->right->right = createNode(4);
    int size;
    int* view = rightSideView(root, &size);
    printf("Right view: ");
    for (int i = 0; i < size; i++) printf("%d ", view[i]);
    printf("\n");
    free(view);
    return 0;
}

⬅ Previous TopicLeft View of a Binary Tree

Next Topic ⮕Top View of a Binary Tree

Comments

Loading comments...