Search a Given Key in BST using JavaScript
Given a binary search tree and a key, determine if the key is present in the tree. If the key is present, return the node containing the key otherwise, return null.
Example:
Input : {15,20,10,8,12,16,25}, Key : 20
Output : 20 found
15
/ \
10 20
/ \ / \
8 12 16 25
Table of Content
- Recursive Approach
- Iterative Approach
Recursive Approach
The call stack is used by the recursive search approach in a BST to manage backtracking. Depending on how the value of the current node compares to the key, the function calls itself while searching for a key, using either the left or right child of the current node.
Example: Recursively searches a binary search tree for a given key, returning the node if found, or null if not
class TreeNode {
constructor(value)
{
this.value = value;
this.left = null;
this.right = null;
}
}
function searchRecursive(node, key)
{
if (node === null)
{
return null;
// Key not found
}
if (key === node.value)
{
return node;
// Key found
} else if (key < node.value)
{
return searchRecursive(node.left, key);
// Search in the left subtree
} else {
return searchRecursive(node.right, key);
// Search in the right subtree
}
}
// Initialize the tree
let root = new TreeNode(15);
root.left = new TreeNode(10);
root.right = new TreeNode(20);
root.left.left = new TreeNode(8);
root.left.right = new TreeNode(12);
root.right.left = new TreeNode(16);
root.right.right = new TreeNode(25);
// Function to check search
// results and print appropriate message
function printSearchResult(result, key)
{
if (result === null) {
console.log(`${key} not found`);
} else {
console.log(`${key} found`);
}
}
// Search using recursive approach and print result
printSearchResult(searchRecursive(root, 16), 16);
printSearchResult(searchRecursive(root, 100), 100);
Output
16 found 100 not found
Time Complexity: O(h)
Space Complexity: O(h)
Iterative Approach
In a BST, the iterative search method uses a loop to manage the traversal and prevents recursion. The call stack required for recursion is removed by this method, which utilizes a variable to track the current node and moves left or right based on comparisons.
Example: Iteratively searches a binary search tree for a given key, returning the node if found, or null if not
class TreeNode {
constructor(value)
{
this.value = value;
this.left = null;
this.right = null;
}
}
function searchIterative(node, key)
{
while (node !== null) {
if (key === node.value)
{
return node;
// Key found
} else if (key < node.value)
{
node = node.left;
// Move to the left subtree
} else {
node = node.right;
// Move to the right subtree
}
}
return null;
// Key not found
}
// Initialize the tree
let root = new TreeNode(15);
root.left = new TreeNode(10);
root.right = new TreeNode(20);
root.left.left = new TreeNode(8);
root.left.right = new TreeNode(12);
root.right.left = new TreeNode(16);
root.right.right = new TreeNode(25);
// Function to check search
// results and print appropriate message
function printSearchResult(result, key)
{
if (result === null)
{
console.log(`${key} value not found`);
} else {
console.log(`${key} value found`);
}
}
// Search using iterative
// approach and print result
printSearchResult(searchIterative(root, 16), 16);
printSearchResult(searchIterative(root, 100), 100);
Output
16 value found 100 value not found
Time Complexity: O(h)
Space Complexity: O(1)