See all coding puzzles and patterns here.

Problem Definition

Given a binary tree, return the list of nodes as seen from the right side of the binary tree.

Example

A test case to verify our solution. 

#        1
#      /   \
#     2     3
#    /       \
#   4         5
#    \
#     6
#    / \
#   7   8
#  /
# 9

nine = Node(9)
seven = Node(7, left=nine)
eight = Node(8)
six = Node(6, left=seven, right=eight)
four = Node(4, right=six)
five = Node(5)
two = Node(2, left=four)
three = Node(3, right=five)
one = Node(1, left=two, right=three)

exp = [1, 3, 5, 6, 8, 9]
assert right_side_view(one) == exp

Solution

This is a graph traversal problem where we need to track the right-most element for each layer, which implies that we must use a breadth-first search.

At every level, we'll append the last (right-most) item in the level to our result. To make sure the right-most element is always last, we'll append the left side to the queue before appending the right side and then always traverse from the front of the queue to its back. 

from collections import deque

def right_side_view(tree: Node) -> list[int]:
    res = []
    q = deque([Node])
    while q:
        res.append(stack[-1].val)
        for i in range(len(q)):
            node = q.popleft()
            if node.left is not None:
                q.append(node.left)
            if node.right is not None:
                q.append(node.right)
    return res

Complexity

Let $n = $ the number of nodes in the tree.

Runtime complexity should be $\Theta(n)$ since we are visiting each node once.

Auxiliary space complexity should be $O(n)$ since in the worst case, the tree is full, which implies that the bottom-most layer of the tree will fill our queue up with $\approx \frac{n}{2}$ items.