Master the principles of Binary Search Trees to efficiently insert, delete, search, and traverse hierarchical data structures used in many classic coding problems.
When you need faster than linear time search in a sorted data structure
Modeling or parsing data with a parent-child structure
When insertions must maintain sorted order without re-sorting
Extracting sorted data from a tree efficiently
Inorder traversal of BST always gives sorted order
O(log n) on average for insert/search/delete in balanced BST
Not handling duplicate values correctly or improperly updating node references
O(h) recursive stack space for operations where h = height of BST
Recursive insertion maintaining BST properties
class TreeNode {
val: number;
left: TreeNode | null;
right: TreeNode | null;
constructor(val = 0, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
function insertIntoBST(root: TreeNode | null, val: number): TreeNode {
if (!root) return new TreeNode(val);
if (val < root.val) {
root.left = insertIntoBST(root.left, val);
} else {
root.right = insertIntoBST(root.right, val);
}
return root;
}Simple recursive search for a value in BST
function searchBST(root: TreeNode | null, val: number): TreeNode | null {
if (!root || root.val === val) return root;
if (val < root.val) {
return searchBST(root.left, val);
} else {
return searchBST(root.right, val);
}
}Retrieve sorted values using inorder traversal
function inorderTraversal(root: TreeNode | null): number[] {
const result: number[] = [];
function traverse(node: TreeNode | null) {
if (!node) return;
traverse(node.left);
result.push(node.val);
traverse(node.right);
}
traverse(root);
return result;
}