Initial Thoughts
Because the tree topography is unknown ahead of time, it is not possible to design an algorithm that visits asymptotically fewer than nodes. Therefore, we should try to aim for a linear time solution. With that in mind, let's consider a few equallyefficient solutions.
Approach #1 DepthFirst Search [Accepted]
Intuition
We can efficiently obtain the righthand view of the binary tree if we visit each node in the proper order.
Algorithm
One of the aforementioned orderings is defined by a depthfirst search in which we always visit the right subtree first. This guarantees that the first time we visit a particular depth of the tree, the node that we are visiting is the rightmost node at that depth. Therefore, we can store the value of the first node that we visit at each depth, ultimately generating a final array of values once we know exactly how many layers are in the tree.
The figure above illustrates one instance of the problem. The red nodes compose the solution from top to bottom, and the edges are labelled in order of visitation.
Complexity Analysis

Time complexity : .
Because a binary tree with only child pointers is directed acyclic graph with only one source node, a traversal of the tree from the root will visit each node exactly once (plus a sublinear amount of leaves, represented as
None
). Each visitation requires only work, so the while loop runs in linear time. Finally, building the array of rightmost values is height of the tree because it is not possible for a righthand view of the tree to contain more nodes than the tree itself. 
Space complexity : .
At worst, our stack will contain a number of nodes close to the height of the tree. Because we are exploring the tree in a depthfirst order, there are never two nodes from different subtrees of the same parent node on the stack at once. Said another way, the entire right subtree of a node will be visited before any nodes of the left subtree are pushed onto the stack. If this logic is applied recursively down the tree, it follows that the stack will be largest when we have reached the end of the tree's longest path (the height of the tree). However, because we know nothing about the tree's topography, the height of the tree may be equivalent to , causing the space complexity to degrade to .
Approach #2 BreadthFirst Search [Accepted]
Intuition
Much like depthfirst search can guarantee that we visit a depth's rightmost node first, breadthfirst search can guarantee that we visit it last.
Algorithm
By performing a breadthfirst search that enqueues the left child before the
right child, we visit each node in each layer from left to right. Therefore,
by retaining only the most recently visited node per depth, we will have
the rightmost node for each depth once we finish the tree traversal. The
algorithm is unchanged, other than swapping out the stack for a
deque
^{1} and removing the containment check before assigning into
rightmost_value_at_depth
.
The figure above illustrates the same instance as before, but solved via breadthfirst search. The red nodes compose the solution from top to bottom, and the edges are labelled in order of visitation.
Complexity Analysis

Time complexity : .
The differences itemized in the Algorithm section do not admit differences in the time complexity analysis between the breadfirst and depthfirst search approaches.

Space complexity : .
Because breadthfirst search visits the tree layerbylayer, the queue will be at its largest immediately before visiting the largest layer. The size of this layer is in the worst case (a complete binary tree).
Footnotes
Analysis written by: @emptyset

The
deque
datatype from thecollections
module supports constant time append/pop from both the head and the tail. If we were to use a Pythonlist
, it would cost us time to remove its head vialist.pop(0)
. ↩