Search in a Binary Search Tree
Easy · tree dfs
You are given the root of a binary search tree (BST) and an integer val. In a BST, every value in a node's left subtree is smaller than the node's own value, every value in its right subtree is larger, and no value appears twice.
Find the node whose value is val and return it. Returning a node means returning the whole subtree that hangs from it (the node and everything below it), written in the same level-order form as the input. If no node holds val, return an empty tree. The input tree may itself be empty.
Examples
Example 1
Input: root = [8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13], val = 3
Output: [3, 1, 6, null, null, 4, 7]
The node holding 3 has children 1 and 6, and 6 has children 4 and 7. Everything below node 3 is returned.
Example 2
Input: root = [4, 2, 7, 1, 3], val = 5
Output: []
No node holds 5, so the answer is an empty tree.
Example 3
Input: root = [5], val = 5
Output: [5]
Constraints
- The number of nodes is in the range [0, 5000], and the height of the tree is at most 1000.
- -10^4 <= Node.val <= 10^4, and all values are distinct.
- The tree is a valid binary search tree.
- -10^4 <= val <= 10^4