Implementing Binary Search Trees
1. Creating BST Class
Example: Basic BST Node Structure
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BST {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new TreeNode(value);
if (this.root === null) {
this.root = newNode;
} else {
this.insertNode(this.root, newNode);
}
}
insertNode(node, newNode) {
if (newNode.value < node.value) {
if (node.left === null) {
node.left = newNode;
} else {
this.insertNode(node.left, newNode);
}
} else {
if (node.right === null) {
node.right = newNode;
} else {
this.insertNode(node.right, newNode);
}
}
}
}
| Property | Description | Default Value |
|---|---|---|
| root | Root node of the binary search tree | null |
Note: The BST class maintains a reference to the root node, which is the starting point for all tree traversals and operations.
2. Inserting Nodes
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| insert(value) | Inserts a new node with the given value into the BST | O(log n) average, O(n) worst-case | O(1) average, O(n) worst-case |
Example: Inserting Nodes into a BST
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new TreeNode(value);
if (this.root === null) {
this.root = newNode;
return this;
}
let current = this.root;
while (true) {
if (value < current.value) {
if (current.left === null) {
current.left = newNode;
break;
}
current = current.left;
} else {
if (current.right === null) {
current.right = newNode;
break;
}
current = current.right;
}
}
return this;
}
}
// Example usage:
const bst = new BinarySearchTree();
bst.insert(10).insert(5).insert(15).insert(3).insert(7);
Note: The insertion process compares the new value with existing nodes to maintain BST property: left subtree contains values less than the node's value, right subtree contains values greater than or equal to the node's value.
3. Searching Nodes
| Method | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| search(root, key) | Finds a node with the specified key in the BST | O(log n) average, O(n) worst-case | O(1) iterative, O(log n) recursive |
| searchRecursive(root, key) | Recursively searches for a node with the specified key | O(log n) average, O(n) worst-case | O(log n) due to call stack |
Example: Searching for a Node
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function search(root, key) {
if (root === null || root.value === key) {
return root;
}
if (key < root.value) {
return search(root.left, key);
} else {
return search(root.right, key);
}
}
// Example usage
const root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(15);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(7);
const foundNode = search(root, 7); // Returns the node with value 7
Note: The search operation leverages the BST property where for every node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater.
4. Deleting Nodes
| Case | Description | Steps |
|---|---|---|
| No Children (Leaf Node) | Node to delete has no children | Simply remove the node from the tree |
| One Child | Node to delete has one child | Replace the node with its child |
| Two Children | Node to delete has two children | Replace node with in-order successor or predecessor |
Example: Deleting a Node with No Children
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BST {
constructor() {
this.root = null;
}
delete(value) {
this.root = this.deleteNode(this.root, value);
}
deleteNode(node, value) {
if (node === null) return null;
if (value < node.value) {
node.left = this.deleteNode(node.left, value);
} else if (value > node.value) {
node.right = this.deleteNode(node.right, value);
} else {
// Node to delete found
if (node.left === null && node.right === null) {
return null; // Remove leaf node
}
}
return node;
}
}
const bst = new BST();
bst.delete(5); // Deletes leaf node with value 5
Example: Deleting a Node with One Child
class BST {
deleteNode(node, value) {
if (node === null) return null;
if (value < node.value) {
node.left = this.deleteNode(node.left, value);
} else if (value > node.value) {
node.right = this.deleteNode(node.right, value);
} else {
// Node to delete found
if (node.left === null) {
return node.right; // Replace with right child
} else if (node.right === null) {
return node.left; // Replace with left child
}
}
return node;
}
}
const bst = new BST();
bst.delete(10); // Deletes node with value 10, which has one child
Example: Deleting a Node with Two Children
class BST {
deleteNode(node, value) {
if (node === null) return null;
if (value < node.value) {
node.left = this.deleteNode(node.left, value);
} else if (value > node.value) {
node.right = this.deleteNode(node.right, value);
} else {
// Node to delete found
if (node.left !== null && node.right !== null) {
// Find in-order successor
const successor = this.findMin(node.right);
node.value = successor.value;
node.right = this.deleteNode(node.right, successor.value);
} else {
return node.left || node.right;
}
}
return node;
}
findMin(node) {
while (node.left !== null) {
node = node.left;
}
return node;
}
}
const bst = new BST();
bst.delete(15); // Deletes node with value 15, which has two children
Note: When deleting a node with two children, the in-order successor (smallest value in right subtree) or predecessor (largest value in left subtree) is used to replace the node's value. This maintains BST properties.
5. Finding Minimum
| Method | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| findMin() | Finds the node with the minimum value in the BST | O(h) | O(1) |
Example: Finding Minimum Value
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BST {
constructor() {
this.root = null;
}
findMin(node = this.root) {
if (!node) return null;
while (node.left) {
node = node.left;
}
return node.value;
}
}
const bst = new BST();
bst.root = new TreeNode(10);
bst.root.left = new TreeNode(5);
bst.root.right = new TreeNode(15);
bst.root.left.left = new TreeNode(3);
bst.root.left.right = new TreeNode(7);
console.log(bst.findMin()); // Output: 3
Note: The minimum value in a BST is always the leftmost node in the tree.
6. Finding Maximum
| Method | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| findMax(node) | Finds the maximum value in the BST by traversing to the rightmost node | O(h) |
O(1) (iterative) or O(h) (recursive) |
Example: Finding Maximum Value
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function findMax(node) {
if (!node) return null;
let current = node;
while (current.right !== null) {
current = current.right;
}
return current.value;
}
// Example usage:
const root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(20);
root.right.right = new TreeNode(30);
console.log(findMax(root)); // Output: 30
Note: The maximum value in a BST is always located at the rightmost node of the tree.
7. Finding Successor
| Method | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| successor(node) | Finds the in-order successor of a given node | O(h) |
O(1) |
Example: Finding Successor in BST
class TreeNode {
constructor(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
function successor(node) {
if (node.right !== null) {
let current = node.right;
while (current.left !== null) {
current = current.left;
}
return current;
}
let successor = null;
let current = root;
while (current !== null) {
if (node.val < current.val) {
successor = current;
current = current.left;
} else {
current = current.right;
}
}
return successor;
}
Note: The successor of a node is the smallest key greater than the node's key in an in-order traversal.
8. Finding Predecessor
| Method | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| findPredecessor(node) | Finds the largest key smaller than the given node's key | O(h) |
O(1) |
Example: Finding Predecessor in BST
class TreeNode {
constructor(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
function findPredecessor(root, target) {
let predecessor = null;
let current = root;
while (current !== null) {
if (target.val < current.val) {
current = current.left;
} else {
predecessor = current;
current = current.right;
}
}
return predecessor;
}
// Example usage:
const root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(15);
root.left.right = new TreeNode(7);
const result = findPredecessor(root, root.left.right); // Node with value 7
console.log(result.val); // Output: 5
Note: The predecessor of a node in a BST is the largest node with a value less than the node's value. If the node has no left subtree, the predecessor is the highest ancestor for which the node is in the right subtree.
9. Validating BST
| Property | Description | Notes |
|---|---|---|
| validBST(root) | Checks if a binary tree is a valid BST | Returns true if valid, false otherwise |
Example: Validating BST
class TreeNode {
constructor(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
function validBST(root) {
function validate(node, min, max) {
if (!node) return true;
if (node.val <= min || node.val >= max) return false;
return validate(node.left, min, node.val) && validate(node.right, node.val, max);
}
return validate(root, -Infinity, Infinity);
}
// Example usage:
const root = new TreeNode(5);
root.left = new TreeNode(3);
root.right = new TreeNode(8);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(4);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(9);
console.log(validBST(root)); // true
Note: A valid BST ensures that for every node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater.
10. Converting to Balanced BST
Converting an unbalanced binary search tree (BST) into a balanced BST involves restructuring the tree to ensure that the height difference between left and right subtrees is at most one for every node. This process is often necessary to maintain optimal performance for search, insertion, and deletion operations.
| Step | Description | Implementation |
|---|---|---|
| In-order Traversal | Traverse the original BST in-order to get a sorted array of values. | |
| Build Balanced BST | Recursively build a balanced BST from the sorted array by selecting the middle element as root. | |
Example: Converting Unbalanced BST to Balanced BST
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// Original unbalanced BST
const root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(15);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(7);
root.right.right = new TreeNode(20);
// Step 1: In-order traversal to get sorted array
const sortedArray = [];
function inOrder(node, result) {
if (node === null) return;
inOrder(node.left, result);
result.push(node.value);
inOrder(node.right, result);
}
inOrder(root, sortedArray);
// Step 2: Build balanced BST from sorted array
function buildBalancedBST(arr, start, end) {
if (start > end) return null;
const mid = Math.floor((start + end) / 2);
const node = new TreeNode(arr[mid]);
node.left = buildBalancedBST(arr, start, mid - 1);
node.right = buildBalancedBST(arr, mid + 1, end);
return node;
}
const balancedRoot = buildBalancedBST(sortedArray, 0, sortedArray.length - 1);
Note: The conversion process ensures that the resulting tree is height-balanced, which guarantees O(log n) time complexity for search, insert, and delete operations.