Right View of a Binary Tree - Iterative Approach

Contents

ProblemExamplesVisualizationSolutionAlgorithmCode

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❯

Case 1: Tree is empty

If the binary tree has no nodes, the right view is simply an empty list. There are no levels to process, so nothing can be seen from the right side.

Case 2: Tree has only one node

In this scenario, there is just the root node and no children. Hence, the right view consists of that single root node, since it's both the top and the rightmost node.

Case 3: Tree has multiple levels with both left and right children

To find the right view, we use a level-order traversal, where we visit each level from left to right. At each level, we track the last node — this is the node visible from the right side. For example, in the tree [1, 2, 3, null, 5, null, 4], we process level by level and pick the last node at each level: 1 from level 1, 3 from level 2, and 4 from level 3.

Case 4: Tree is right skewed

If the tree has only right children at each level, then all the nodes form the right view because each node is the only one in its level and also the rightmost. For example, [1, null, 2, null, 3] yields [1, 2, 3] as the right view.

Case 5: Tree is left skewed

When the tree contains only left children at each level, even then, the last (and only) node of each level becomes part of the right view. For instance, [1, 2, null, 3] will result in [1, 2, 3] as each level still has one node, and it's considered the rightmost by default.

Algorithm Steps❯

  1. Given a binary tree, if the tree is empty, return an empty result.
  2. Initialize a queue and enqueue the root node.
  3. While the queue is not empty, determine the number of nodes at the current level (levelSize).
  4. For each node in the current level, dequeue a node.
  5. 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.
  6. Enqueue the left and then right child of the node (if they exist) for processing in the next level.
  7. Repeat until all levels are processed; the recorded values form the right view of the binary tree.

Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rightView(root):
    if not root:
        return []
    result = []
    queue = [root]
    while queue:
        levelSize = len(queue)
        for i in range(levelSize):
            node = queue.pop(0)
            if i == levelSize - 1:
                result.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return result

if __name__ == '__main__':
    # Construct binary tree:
    #         1
    #        / \
    #       2   3
    #        \    \
    #         5    4
    root = TreeNode(1, TreeNode(2, None, TreeNode(5)), TreeNode(3, None, TreeNode(4)))
    print(rightView(root))