Search in a Binary Search Tree
You are given the root of a binary search tree and an integer val. Find the node whose value equals val and return the subtree rooted at that node. If there is no such node, return null.
Constraints:
- The number of nodes is in the range
[1, 5000]. 1 <= Node.val <= 10^7, the root is a valid BST, and1 <= val <= 10^7.
Intuition
1 82 / \3 4 124 / \ / \5 2 6 10 14Recall the BST property: for every node, everything in the left subtree is smaller and everything in the right subtree is larger. Because of it, one comparison at a node tells us which half of the tree to ignore.
Searching for 6: at 8, 6 is smaller, so go left. At 4, 6 is larger, so go right. At 6, found. We never look at the other half, exactly like binary search on a sorted array.
Approach: Walk Down One Path
- Start at the root.
- While the node exists and its value is not
val:- If
valis smaller, move to the left child. - Otherwise move to the right child.
- If
- Return the node. It is either the match or
null.
No recursion or extra memory is needed. A plain loop is enough because we follow a single root-to-leaf path.
Code
class Solution {public:TreeNode* searchBST(TreeNode* root, int val) {while (root != nullptr && root->val != val) {root = val < root->val ? root->left : root->right;}return root;}};
Complexity
We follow one root-to-leaf path. That is O(log n) for a balanced BST and O(n) for a skewed one.
The iterative loop uses no extra memory. A recursive version would use O(h) stack.