Right Side View of a Binary Tree

You are given a binary tree. Your task is to compute the right side view of the tree. The right side view of a binary tree is the set of nodes that are visible when the tree is viewed from the right side.

The binary tree is provided in level-order format as a sequence of tokens separated by spaces. If a node is missing, it is represented by the token null.

Example:

Input: 1 2 3 null 5 null 4
Output: 1 3 4

In the above example, the tree is constructed as:

\(\begingroup\begin{array}{c} 1 \\ / \\ 2 3 \\ \ \ \backslash \\ \ 5 4 \end{array}\endgroup\)

The right side view of the tree is \( [1, 3, 4] \).

Note: An efficient solution should run in \( O(n) \) time where \( n \) is the number of nodes in the tree.

inputFormat

The first line contains an integer \(T\), the number of test cases. Each of the next \(T\) lines represents one test case. Each test case is given as a level-order traversal of a binary tree. The values are separated by spaces and a missing (null) node is represented by the token null.

Example:

5
1 2 3 null 5 null 4
1 2 3
1
null
1 2 3 4 5

outputFormat

For each test case, output a single line containing the values of the nodes visible from the right side of the binary tree. The values should be printed in order and separated by a single space. If the tree is empty, output an empty line.

## sample

3
1 2 3 null 5 null 4
1 2 3
1

1 3 4
1 3
1

</p>