Dare2Solve
Given the root of a binary search tree (BST) and an integer value, the task is to search the BST for the node that contains the given value. If the value is found, return the corresponding node. If the value is not found in the tree, return null
or None
.
In a binary search tree, for any given node, the values of all the nodes in its left subtree are smaller, and the values of all the nodes in its right subtree are larger. This property makes searching in a BST efficient, as you can eliminate half of the tree at each step depending on the value you are searching for.
null
or None
.O(h), where h is the height of the tree. In the worst case, this can be O(n) for a skewed tree, but in a balanced tree, it would be O(log n).
O(1) for the iterative approach, as no additional space is required other than pointers. If using a recursive approach, the space complexity would be O(h) due to the function call stack.
/**
* Definition for a binary tree node.
* struct TreeNode {
* 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) {
TreeNode* current = root;
while (current != nullptr) {
if (val == current->val) {
return current;
} else if (val < current->val) {
current = current->left;
} else {
current = current->right;
}
}
return nullptr;
}
};
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def searchBST(self, root: TreeNode, val: int) -> TreeNode:
current = root
while current:
if val == current.val:
return current
elif val < current.val:
current = current.left
else:
current = current.right
return None
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
TreeNode current = root;
while (current != null) {
if (val == current.val) {
return current;
} else if (val < current.val) {
current = current.left;
} else {
current = current.right;
}
}
return null;
}
}
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
var searchBST = function (root, val) {
let current = root;
while (current) {
if (val === current.val) {
return current;
} else if (val < current?.val) {
current = current.left;
} else {
current = current.right;
}
}
return null;
};