Learn how to implement an efficient recursive search algorithm for Binary Search Trees. Master the technique of leveraging BST properties to optimize search operations.
A Binary Search Tree has these key properties:
Search operation advantages:
class BSTNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
search(value) {
return this._searchRecursive(this.root, value);
}
_searchRecursive(node, value) {
// Base case 1: Empty tree or not found
if (node === null) {
return null;
}
// Base case 2: Value found
if (node.value === value) {
return node;
}
// Recursive cases
}
// Inside _searchRecursive after base cases
if (value < node.value) {
// Search left subtree (smaller values)
return this._searchRecursive(node.left, value);
} else {
// Search right subtree (larger values)
return this._searchRecursive(node.right, value);
}
class BST {
constructor() {
this.root = null;
}
search(value) {
return this._searchRecursive(this.root, value);
}
_searchRecursive(node, value) {
// Base case 1: Empty tree or not found
if (node === null) {
return null;
}
// Base case 2: Value found
if (node.value === value) {
return node;
}
// Recursive cases
if (value < node.value) {
// Search left subtree (smaller values)
return this._searchRecursive(node.left, value);
} else {
// Search right subtree (larger values)
return this._searchRecursive(node.right, value);
}
}
}
Now that you've learned how to implement a recursive search in a Binary Search Tree, try these challenges to reinforce your understanding.
Implement two methods to find the minimum and maximum values in a BST.
findMin() to find the minimum value in the BSTfindMax() to find the maximum value in the BSTclass BST {
// ... existing implementation
findMin() {
// Your code here
}
_findMinRecursive(node) {
// Your code here
}
findMax() {
// Your code here
}
_findMaxRecursive(node) {
// Your code here
}
}
Implement a method that counts how many nodes have values in a given range [min, max].
countNodesInRange(min, max) that returns the count of nodes with values between min and max (inclusive)class BST {
// ... existing implementation
countNodesInRange(min, max) {
return this._countNodesInRangeRecursive(this.root, min, max);
}
_countNodesInRangeRecursive(node, min, max) {
// Your code here
}
}
If you want more practice with BST operations, check out these LeetCode problems: