Search in a Binary Search Tree
Search for a given value in a binary search tree and return the node if found.
Input format
The first line contains level-order tokens. The second line contains X.
Output format
Find the subtree rooted at X and print its preorder traversal. If X not found, print -1.
Constraints
- Values fit in a 64-bit signed integer
- Trailing whitespace and a trailing newline are ignored by the judge
Read from stdin, write to stdout. Sample cases below show the exact format.
Sample cases
Example 1
Input
35 3 58 1 34 40 83 N N 29 N 38 55 79 99 16 N N N 54 N 61 N N N N N N N N 74 70 75
79Expected output
79 61 74 70 75Example 2
Input
26 N 52
26Expected output
26 52