Initial Thoughts

Because the tree topography is unknown ahead of time, it is not possible to\ndesign an algorithm that visits asymptotically fewer than $$n$$ nodes.\nTherefore, we should try to aim for a linear time solution. With that in\nmind, let\'s consider a few equally-efficient solutions.

Approach #1 Depth-First Search [Accepted]

Intuition

We can efficiently obtain the right-hand view of the binary tree if we visit\neach node in the proper order.

Algorithm

One of the aforementioned orderings is defined by a depth-first search in\nwhich we always visit the right subtree first. This guarantees that the first\ntime we visit a particular depth of the tree, the node that we are visiting\nis the rightmost node at that depth. Therefore, we can store the value of the\nfirst node that we visit at each depth, ultimately generating a final array\nof values once we know exactly how many layers are in the tree.

The figure above illustrates one instance of the problem. The red nodes\ncompose the solution from top to bottom, and the edges are labelled in order\nof visitation.

Complexity Analysis

\n
• \n

  Time complexity : $$O(n)$$ .

  \n

  Because a binary tree with only child pointers is directed acyclic graph\nwith only one source node, a traversal of the tree from the root will visit\neach node exactly once (plus a sublinear amount of leaves, represented as\nNone). Each visitation requires only $$O(1)$$ work, so the while loop\nruns in linear time. Finally, building the array of rightmost values is\n $$O($$ height of the tree $$) = O(n)$$ because it is not possible for a\nright-hand view of the tree to contain more nodes than the tree itself.

  \n
\n
• \n

  Space complexity : $$O(n)$$ .

  \n

  At worst, our stack will contain a number of nodes close to the height of\nthe tree. Because we are exploring the tree in a depth-first order, there\nare never two nodes from different subtrees of the same parent node on the\nstack at once. Said another way, the entire right subtree of a node will be\nvisited before any nodes of the left subtree are pushed onto the stack. If\nthis logic is applied recursively down the tree, it follows that the stack\nwill be largest when we have reached the end of the tree\'s longest path\n(the height of the tree). However, because we know nothing about the tree\'s\ntopography, the height of the tree may be equivalent to $$n$$ , causing the\nspace complexity to degrade to $$O(n)$$ .

  \n
\n

Approach #2 Breadth-First Search [Accepted]

Intuition

Much like depth-first search can guarantee that we visit a depth\'s rightmost\nnode first, breadth-first search can guarantee that we visit it last.

Algorithm

By performing a breadth-first search that enqueues the left child before the\nright child, we visit each node in each layer from left to right. Therefore,\nby retaining only the most recently visited node per depth, we will have\nthe rightmost node for each depth once we finish the tree traversal. The\nalgorithm is unchanged, other than swapping out the stack for a\ndeque¹ and removing the containment check before assigning into\nrightmost_value_at_depth.

The figure above illustrates the same instance as before, but solved via\nbreadth-first search. The red nodes compose the solution from top to bottom,\nand the edges are labelled in order of visitation.

Complexity Analysis

\n
• \n

  Time complexity : $$O(n)$$ .

  \n

  The differences itemized in the Algorithm section do not admit\ndifferences in the time complexity analysis between the bread-first and\ndepth-first search approaches.

  \n
\n
• \n

  Space complexity : $$O(n)$$ .

  \n

  Because breadth-first search visits the tree layer-by-layer, the queue\nwill be at its largest immediately before visiting the largest layer. The\nsize of this layer is $$0.5n = O(n)$$ in the worst case (a complete binary\ntree).

  \n
\n

Footnotes

Analysis written by: @emptyset