deepSWE.io

Binary Tree Right Side View

TreesBFS / DFS

20 min

Problem Statement

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.

Example

Example 1:

Input: root = [1,2,3,null,5,null,4]

Output: [1,3,4]

Solution 1: Breadth-First Search (BFS)

The BFS approach traverses the tree level by level. For each level, the rightmost node is the one we can see from the right side.

Algorithm Steps

Create a queue and add the root node.
While the queue is not empty, get the number of nodes at the current level.
For each level, the last node is the rightmost one. Add its value to the result list.
Enqueue the children of the nodes at the current level.

Right Side View: []

Start of level. Level size: 1.

Binary Tree Right Side View Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
            
        res = []
        q = deque([root])
        
        while q:
            right_side = None
            q_len = len(q)
            
            for i in range(q_len):
                node = q.popleft()
                if node:
                    right_side = node
                    q.append(node.left)
                    q.append(node.right)
            
            if right_side:
                res.append(right_side.val)
                
        return res

Solution 2: Depth-First Search (DFS)

The DFS approach traverses the tree, keeping track of the current level. The first time we visit a level, we add the node's value to our result list. Since we traverse the right subtree first, the first node we see at each level will be the rightmost one.

Algorithm Steps

Create a recursive function that takes the current node and level as arguments.
If the current level is equal to the size of our result list, it means we're visiting this level for the first time. Add the node's value to the list.
Recursively call the function on the right child first, then the left child.

Right Side View: []

Visiting node 1 at level 0.

Binary Tree Right Side View Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        
        def dfs(node, level):
            if not node:
                return
            
            if level == len(res):
                res.append(node.val)
            
            dfs(node.right, level + 1)
            dfs(node.left, level + 1)
            
        dfs(root, 0)
        return res