Problem Statement:
You are given the root of a binary search tree (BST) and an integer val.
Find the node in the BST that the node’s value equals val and return the subtree rooted with that node. If such a node does not exist, return null.
Examples:
Example 1:
Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]
Example 2:
Input: root = [4,2,7,1,3], val = 5
Output: []
Constraints:
- The number of nodes in the tree is in the range
[1, 5000]. 1 <= Node.val <= 107rootis a binary search tree.1 <= val <= 107
Approach 1: Top-Down Method
- If the current node’s value
equalsthe targetval, we store it as the answer. - If the current value is
lessthan the target, we move to the right subtree. - If the current value is
greaterthan the target, we move to the left subtree. - We return the node if found, otherwise return
null.
Time Complexity:
Time Complexity = O(log n)
Space Complexity:
Space Complexity = O(log n)
Dry Run
Function Call: searchBST(root, val = 6) where
root = Node(4)
├── left: Node(2)
│ ├── left: Node(1)
│ └── right: Node(3)
└── right: Node(7)
├── left: Node(6)
└── right: Node(9)
Step 1:
→ Call traversal(curr = 4)
→ curr.val = 4, which is less than val = 6
→ So, move to curr.right
→ Call traversal(curr = 7)
→ curr.val = 7, which is greater than val = 6
→ So, move to curr.left
→ Call traversal(curr = 6)
→ curr.val == val (6 == 6)
→ ans = curr (Node with value 6)
→ traversal ends
Final Result: return Node with value = 6
root = Node(4)
├── left: Node(2)
│ ├── left: Node(1)
│ └── right: Node(3)
└── right: Node(7)
├── left: Node(6)
└── right: Node(9)
Step 1:
→ Call traversal(curr = 4)
→ curr.val = 4, which is less than val = 6
→ So, move to curr.right
→ Call traversal(curr = 7)
→ curr.val = 7, which is greater than val = 6
→ So, move to curr.left
→ Call traversal(curr = 6)
→ curr.val == val (6 == 6)
→ ans = curr (Node with value 6)
→ traversal ends
Final Result: return Node with value = 6
var searchBST = function(root, val) {
let ans = null;
let traversal = (curr) => {
if (curr.val == val) {
ans = curr;
} else {
if (curr.val < val) {
curr.right && traversal(curr.right);
} else {
curr.left && traversal(curr.left);
}
}
}
traversal(root);
return ans;
};
def searchBST(root, val):
ans = None
def traversal(curr):
nonlocal ans
if not curr:
return
if curr.val == val:
ans = curr
elif curr.val < val:
traversal(curr.right)
else:
traversal(curr.left)
traversal(root)
return ans
public TreeNode searchBST(TreeNode root, int val) {
TreeNode[] ans = new TreeNode[1];
voidTraversal(root, val, ans);
return ans[0];
}
private void voidTraversal(TreeNode curr, int val, TreeNode[] ans) {
if (curr == null) return;
if (curr.val == val) {
ans[0] = curr;
} else if (curr.val < val) {
voidTraversal(curr.right, val, ans);
} else {
voidTraversal(curr.left, val, ans);
}
}
TreeNode* searchBST(TreeNode* root, int val) {
TreeNode* ans = nullptr;
function traversal = [&](TreeNode* curr) {
if (!curr) return;
if (curr->val == val) {
ans = curr;
} else {
if (curr->val < val) {
traversal(curr->right);
} else {
traversal(curr->left);
}
}
};
traversal(root);
return ans;
}
TreeNode* searchBST(TreeNode* root, int val) {
if (root == NULL) return NULL;
if (root->val == val)
return root;
else if (root->val < val)
return searchBST(root->right, val);
else
return searchBST(root->left, val);
}
public TreeNode SearchBST(TreeNode root, int val) {
TreeNode ans = null;
void Traversal(TreeNode curr) {
if (curr == null) return;
if (curr.val == val) {
ans = curr;
} else {
if (curr.val < val)
Traversal(curr.right);
else
Traversal(curr.left);
}
}
Traversal(root);
return ans;
}
Approach 2: Bottom-Up Method
- Best Case: If the current node is
nullor matches the targetval, return it. - Recursive Step:
- If the current node's value is less than
val, search in the right subtree. - If greater, search in the left subtree.
- If the current node's value is less than
Time Complexity:
Time Complexity = O(h), where h is the height of the tree.
- Best:
O(log n)(balanced tree) - Worst:
O(n)(skewed tree)
Space Complexity:
Space Complexity = O(h)
Dry Run
Function Call: searchBST(root, val = 6) where
root = Node(4)
├── left: Node(2)
│ ├── left: Node(1)
│ └── right: Node(3)
└── right: Node(7)
├── left: Node(6)
└── right: Node(9)
Step 1:
→ searchBST(Node(4), 6)
→ 4 < 6 → go right
Step 2:
→ searchBST(Node(7), 6)
→ 7 > 6 → go left
Step 3:
→ searchBST(Node(6), 6)
→ 6 == 6 → return Node(6)
Final Result: return Node with value = 6
root = Node(4)
├── left: Node(2)
│ ├── left: Node(1)
│ └── right: Node(3)
└── right: Node(7)
├── left: Node(6)
└── right: Node(9)
Step 1:
→ searchBST(Node(4), 6)
→ 4 < 6 → go right
Step 2:
→ searchBST(Node(7), 6)
→ 7 > 6 → go left
Step 3:
→ searchBST(Node(6), 6)
→ 6 == 6 → return Node(6)
Final Result: return Node with value = 6
var searchBST = function(root, val) {
if(!root || root.val === val) return root;
return root.val < val ?
searchBST(root.right, val) :
searchBST(root.left, val);
};
def searchBST(root, val):
if not root or root.val == val:
return root
return searchBST(root.right, val) if root.val < val else searchBST(root.left, val)
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) return root;
return root.val < val ?
searchBST(root.right, val) :
searchBST(root.left, val);
}
TreeNode* searchBST(TreeNode* root, int val) {
if (!root || root->val == val) return root;
return root->val < val ?
searchBST(root->right, val) :
searchBST(root->left, val);
}
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
struct TreeNode* searchBST(struct TreeNode* root, int val) {
if (root == NULL || root->val == val) return root;
return root->val < val ?
searchBST(root->right, val) :
searchBST(root->left, val);
}
public TreeNode SearchBST(TreeNode root, int val) {
if (root == null || root.val == val) return root;
return root.val < val ?
SearchBST(root.right, val) :
SearchBST(root.left, val);
}
