What the tree looks like from the right

Stand to the right of a binary tree and look at it. Report the values you can see, top to bottom: the rightmost node at each level.

Worked example#

      1
     / \
    2   3
     \   \
      5   4

From the right you see the 1, then the 3, then the 4. So the answer is 1 3 4.

Note the 5 is hidden behind the 4, and the 2 behind the 3. Only one node per level is visible, and it is the last one on that level.

The idea#

"The rightmost node at each level" is doing all the work in that sentence. Walk the tree level by level, and take the last node of each level.

The one piece you need beyond plain level order is knowing where a level ends. The neat way: before you start draining the queue, note how many nodes are in it. That count is exactly one level, because nothing you add during the pass belongs to it.

while the queue is not empty:
    n = size of the queue        # one whole level
    for i in 1..n:
        take a node
        if i == n: record it     # the last one on this level
        add its children

That "note the size first" trick is worth keeping. It turns level order into "level by level", which is what almost every level-based tree question actually needs.

A left view is the same code#

Record the first node of each level instead of the last. Nothing else changes. Recognising that two questions are one question is most of what makes tree problems quick.

Constraints#

• 0 <= number of nodes <= 100000

About the input#

The tree is written level by level with null for a missing child, the count first.