Sponsored
Sponsored
This approach uses the recursive traversal of the BST properties. It checks if the current node's value is equal to the target value. If it is, it returns the subtree rooted at the current node. If the target value is less than the current node, it recurses into the left subtree; if greater, it recurses into the right subtree. This method leverages the BST's inherent properties to narrow down the search.
Time Complexity: O(h) where h is the height of the tree, as we traverse from the root to a leaf.
Space Complexity: O(h) due to the recursion stack.
1public class TreeNode {
2 public int val;
3 public TreeNode left;
4 public TreeNode right;
5 public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
6 this.val = val;
7 this.left = left;
8 this.right = right;
9 }
10}
11
12public class Solution {
13 public TreeNode SearchBST(TreeNode root, int val) {
14 if (root == null || root.val == val) {
15 return root;
16 }
17 if (val < root.val) {
18 return SearchBST(root.left, val);
19 }
20 return SearchBST(root.right, val);
21 }
22}The C# code provided implements a recursive method SearchBST to perform a BST search. It either returns the node with the same value as val or traverses the left/right subtree based on the comparison.
In this approach, we use an iterative solution instead of recursion to save stack space. Starting from the root, we use a loop to traverse the tree. At each node, we check if it matches the target value. If it matches, we return the node; if not, we decide to move to the left or right child based on the BST property. The absence of a matching node returns null.
Time Complexity: O(h) where h is tree height.
Space Complexity: O(1) since we're only using a few extra pointers.
1public:
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
while (root != nullptr && root->val != val) {
if (val < root->val) {
root = root->left;
} else {
root = root->right;
}
}
return root;
}
};This C++ iterative function searchBST utilizes a while loop to iterate over the tree nodes, adapting the path taken at each step according to BST properties, until it finds the target or the search ends.