You are given the root of a binary search tree (BST) and an integer val.
Find the node in the BST such that the node’s value equals val, and return the subtree rooted at that node. If such a node does not exist, return null.
Input / Output
Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]
Input: root = [4,2,7,1,3], val = 5
Output: []
Approach
- This is a classic BST property search problem.
- At each node:
- If the node is
null, returnnull. - If
node.val === val, return node. - If
val < node.val, search the left subtree. - If
val > node.val, search the right subtree.
- If the node is
- This takes advantage of the BST property for efficient O(log n) time search on average.
Time & Space Complexity
- Time Complexity: O(h), where h is the height of the tree (O(log n) for balanced, O(n) for skewed trees)
- Space Complexity: O(h) due to recursion stack
var searchBST = function (root, val) {
if (!root || root.val === val) return root;
return root.val < val ?
searchBST(root.right, val) :
searchBST(root.left, val);
};
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* searchBST(TreeNode* root, int val) {
if (!root || root->val == val) return root;
return val < root->val ? searchBST(root->left, val) : searchBST(root->right, val);
}
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode* searchBST(struct TreeNode* root, int val) {
if (!root || root->val == val) return root;
return val < root->val ? searchBST(root->left, val) : searchBST(root->right, val);
}
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) return root;
return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
}
}
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def searchBST(root, val):
if not root or root.val == val:
return root
return searchBST(root.left, val) if val < root.val else searchBST(root.right, val)
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public TreeNode SearchBST(TreeNode root, int val) {
if (root == null || root.val == val) return root;
return val < root.val ? SearchBST(root.left, val) : SearchBST(root.right, val);
}
}
