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 {
int value;
BSTNode left;
BSTNode right;
BSTNode(int value) {
this.value = value;
this.left = null;
this.right = null;
}
}
public BSTNode search(int value) {
return searchRecursive(root, value);
}
private BSTNode searchRecursive(BSTNode node, int 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 searchRecursive(node.left, value);
} else {
// Search right subtree (larger values)
return searchRecursive(node.right, value);
}
class BST {
BSTNode root;
public BST() {
this.root = null;
}
public BSTNode search(int value) {
return searchRecursive(root, value);
}
private BSTNode searchRecursive(BSTNode node, int value) {
if (node == null) {
return null;
}
if (node.value == value) {
return node;
}
if (value < node.value) {
return searchRecursive(node.left, value);
} else {
return 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
public BSTNode findMin() {
return findMinRecursive(root);
}
private BSTNode findMinRecursive(BSTNode node) {
if (node == null || node.left == null) {
return node;
}
return findMinRecursive(node.left);
}
public BSTNode findMax() {
return findMaxRecursive(root);
}
private BSTNode findMaxRecursive(BSTNode node) {
if (node == null || node.right == null) {
return node;
}
return findMaxRecursive(node.right);
}
}
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
public int countNodesInRange(int min, int max) {
return countNodesInRangeRecursive(root, min, max);
}
private int countNodesInRangeRecursive(BSTNode node, int min, int max) {
if (node == null) {
return 0;
}
if (node.value < min) {
return countNodesInRangeRecursive(node.right, min, max);
} else if (node.value > max) {
return countNodesInRangeRecursive(node.left, min, max);
} else {
return 1 + countNodesInRangeRecursive(node.left, min, max) + countNodesInRangeRecursive(node.right, min, max);
}
}
}
If you want more practice with BST operations, check out these LeetCode problems: