Look Up a Key and Return Its Whole Subtree
Implement findSubtree
You are given the root of a binary search tree (every node's left subtree holds smaller values and its right subtree holds larger values, and all values are distinct) and an integer key. Find the node that holds key and return it — that is, return the whole subtree that starts at that node. If no node holds key, return an empty tree.
You can search every node like in any binary tree, but the ordering lets you discard one whole side at each step.
Example 1:
Input: root = [40,20,60,10,30,50,70,null,null,25,35], key = 30
Output: [30,25,35]
Example 2:
Input: root = [40,20,60,10,30,50,70,null,null,25,35], key = 45
Output: []
Example 3:
Input: root = [40,20,60,10,30,50,70,null,null,25,35], key = 60
Output: [60,50,70]
+ 14 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ number of nodes ≤ 100; all node values are distinct, 0 ≤ node.val ≤ 1000 - ●
The tree is a binary search tree: for every node, all values in its left subtree are smaller and all values in its right subtree are larger. It is given as its root node (null for an empty tree) - ●
key is any integer between 0 and 1000 (it may or may not be in the tree) - ●
Return the node holding key, i.e. the whole subtree that starts there (it is checked as a level-order list). If key is not in the tree, return an empty tree
root =
key =