Search a BST
You get the root of a binary search tree and a number val. In a binary search tree (BST), every value in a node's left subtree (its left child and everything below it) is smaller than the node's value and every value in its right subtree is larger, so no value appears twice.
Find the node whose value is val and return that node itself, not a copy and not its value: whoever called then has the node and everything below it. When no node holds val, return None. An empty tree (root is None) holds nothing.
Trees in the examples are written in level order, the way build_tree reads them: the root, then each row from left to right, with None where a child is missing. An output in that form is the subtree under the returned node.
root = [8, 4, 12, 2, 6, 10, 14], val = 4Output[4, 2, 6]The node holding 4, with its subtree: 2 on its left and 6 on its right.
root = [8, 4, 12, 2, 6, 10, 14], val = 7OutputNone7 is smaller than 8, so go left to 4; larger than 4, so go right to 6; larger than 6, but 6 has no right child. No node holds 7.
root = [8, 4, 12, 2, 6, 10, 14], val = 14Output[14]14 is a leaf, a node with no children, so its subtree is the node alone.
0 ≤ number of nodes ≤ 2 × 105
-109 ≤ node value, val ≤ 109; node values are all different.
The tree is at most 500 levels deep.
The function may be called many times on the same tree.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.