Beginner LevelData Structures & Algorithms
What is a Binary Search Tree (BST) and how do Search, Insert, and Delete work?
ā Interview Prompt: Explain BST invariant, average O(log N) vs worst-case O(N) operations, and BST Search, Insert, and Delete algorithms.
A Binary Search Tree (BST) maintains the BST invariant: for every node, all values in its left subtree are less than the node, and all values in its right subtree are greater than the node.
Operations:
ā¢
Search: Compare target to current node; go left if smaller, right if larger. $O(H)$ where $H$ = height.
ā¢
Insert: Traverse to the correct position and add the node. $O(H)$.
ā¢
Delete: Three cases:
1
Leaf ā simply remove.
2
One child ā replace node with child.
3
Two children ā replace with in-order successor (smallest in right subtree) and delete successor.
ā¢
Average case: $O(\log N)$ for balanced BST. Worst case: $O(N)$ for skewed (sorted insertion).
Code Implementation Example
typescript
function searchBST(root: TreeNode | null, val: number): TreeNode | null {
if (!root || root.val === val) return root;
return val < root.val
? searchBST(root.left, val)
: searchBST(root.right, val);
}
function insertBST(root: TreeNode | null, val: number): TreeNode {
if (!root) return new TreeNode(val);
if (val < root.val) root.left = insertBST(root.left, val);
else root.right = insertBST(root.right, val);
return root;
}š”BST search and insert maintaining the BST invariant.
šÆ Interview Key Takeaway
BST gives O(log N) average-case operations. Always consider balanced BST variants (AVL, Red-Black) for guaranteed O(log N) in production.
#DSA#BST#Binary Search Tree#Trees#Beginner
Back to all Data Structures & Algorithms Questionsā