A records vault files dossiers as they arrive, each tagged with a unique integer code. Dossiers are inserted one at a time in arrival order using the standard binary-search-tree rule: the first dossier becomes the root, and every later dossier is walked down from the root, moving to the left child whenever its code is smaller than the current node's code and to the right child whenever it is larger, until it reaches an empty slot where it is filed as a brand-new node.
An archivist later wants to pull an entire branch out of the vault: given a query code, find the dossier carrying that code and retrieve everything filed beneath it too -- the whole subtree rooted at that dossier. Report the retrieved codes as a preorder walk of that subtree (the dossier itself, then its entire left branch, then its entire right branch). If no dossier with the query code exists, report that the branch was not found.
n, the number of dossiers filed.n space-separated distinct integers, the codes in the order they were filed.q, the query code.If a dossier with code q exists in the vault, print the preorder traversal (node, then left subtree, then right subtree) of the subtree rooted at that dossier, as space-separated integers. Otherwise, print -1.
q satisfy -100000 <= value <= 100000.Example 1
Input
7 5 3 8 1 4 7 9 3
Expected
3 1 4
Explanation
Inserting 5, 3, 8, 1, 4, 7, 9 in order builds a tree with root 5 (left child 3, right child 8); node 3 has left child 1 and right child 4; node 8 has left child 7 and right child 9. Querying code 3 finds that node, whose subtree contains 3, 1, and 4, giving preorder walk "3 1 4".
Example 2
Input
7 5 3 8 1 4 7 9 6
Expected
-1
Explanation
Using the same tree built in Example 1, no dossier with code 6 was ever filed, so the branch cannot be found and the output is -1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →