Binary Search Tree
A binary search tree (BST) is a binary tree with the property: for every node, all nodes in its left subtree have smaller values, and all nodes in its right subtree have larger values. This enables efficient searching, insertion, and deletion (O(log n) average).
BST property: left < root < right (assuming no duplicates).
Search in BST:
public TreeNode search(TreeNode root, int val) {
if (root == null || root.val == val) return root;
if (val < root.val) return search(root.left, val);
return search(root.right, val);
}
Insertion in BST:
public TreeNode insert(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
if (val < root.val) root.left = insert(root.left, val);
else if (val > root.val) root.right = insert(root.right, val);
return root;
}
Inorder traversal of BST gives sorted order.
Two Minute Drill
- BST: left < node < right for all nodes.
- Search: O(log n) average, O(n) worst-case if unbalanced.
- Insert: similar to search, then add as leaf.
- Inorder traversal yields sorted sequence.
- Foundation for efficient dictionaries, maps, sets.
Need more clarification?
Drop us an email at career@quipoinfotech.com