Solutions

# Level based traversal of the tree, keeping track of the rightmost node at each level.
# trees


# DFS - O(n) time, O(h) space where h is the height of the tree
def rightSideView(root: Optional[TreeNode]) -> List[int]:
    res = [[]]

    def dfs(node: TreeNode, level: int):
        if not node:
            return

        if len(res) == level:
            res.append([])

        res[level].append(node.val)
        # First left and then right,
        # so that the rightmost element is the last one in the list for each level
        dfs(node.left, level+1)
        dfs(node.right, level+1)

    dfs(root, 0)

    # Take the last element of each level, which is the rightmost element
    out = []
    for level in res:
        if level:
            out.append(level[-1])
    return out


# BFS - O(n) time, O(w) space where w is the maximum width of the tree
from collections import deque
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
    res = []
    q = deque([root])

    while q:
        rightSide = None
        qLen = len(q)

        for _ in range(qLen):
            node = q.popleft()
            if node:
                # The rightmost node of the level will be the last one we see in the loop,
                # so we keep updating rightSide until the end of the level
                rightSide = node
                q.append(node.left)
                q.append(node.right)
        if rightSide:
            res.append(rightSide.val)
    return res