Path to a Node in a Binary Tree

Given a binary tree and an integer target, your task is to find the unique path from the root node to the node with the target value using depth-first search. The binary tree is provided in level-order format, where missing nodes are indicated by the string null. It is guaranteed that the target exists in the tree.

The answer should output the values in the path separated by a single space.

The relation between the nodes in the tree is defined by the following structure:

[ \texttt{TreeNode} := { \texttt{val},; \texttt{left},; \texttt{right} } ]

where left and right refer to the left and right children of a node, respectively.

inputFormat

The input is given in three parts from standard input:

1. An integer N that represents the total number of tokens representing the nodes in the tree, including the null placeholders.
2. A line containing N tokens separated by spaces. These tokens represent the level-order traversal of the binary tree. The token null denotes that a node is missing.
3. An integer that denotes the target node value.

outputFormat

Print a single line to standard output containing the values from the root to the target node, separated by single spaces.

3
1 2 3
3

1 3