Binary Tree Right Side View

Problem Statement

You are given the root of a binary tree. Return only the values of the nodes that are visible from the right side of the tree, ordered from top to bottom.

Example 1:

# 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


# Input: root = [1,2,3]
# Output: [1, 3]

Example 2:

# 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


# Input: root = [1,2,3,4,5,6,7]
# Output: [1,3,7]

Constraints:

  • 0 <= number of nodes in the tree <= 100
  • -100 <= Node.val <= 100

You should aim for a solution with O(n) time and O(n) space, where n is the number of nodes in the given tree.

You should aim for a solution with O(n) time and O(n) space, where n is the number of nodes in the given tree.

Hint 1

In the right-side view of a tree, can you identify the nodes that are visible? Maybe you could traverse the tree level by level and determine which nodes are visible from the right side.

Hint 2

The nodes visible in the right-side view are the last nodes at each level of the tree. Can you think of an algorithm to identify these nodes? Maybe an algorithm that can traverse the tree level by level.

Hint 3

We can use the Breadth First Search (BFS) algorithm to traverse the tree level by level. Once we completely visit a level, we take the last node of that level and add it to the result array. After processing all levels, we return the result.

Solution

from collections import deque
from typing import List, Optional


# 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




def right_side_view_dfs(root: Optional[TreeNode]) -> List[int]:
    res = []


    def dfs(node: Optional[TreeNode], depth: int):
        if not node:
            return


        if depth == len(res):
            res.append(node.val)


        dfs(node.right, depth + 1)
        dfs(node.left, depth + 1)


    dfs(root, 0)
    return res

Time complexity: O(n) Space complexity: O(n)