Unit 3: Trees & Dynamic Programming
Binary Search Tree (BST) Properties
14 min read · 68% complete
Explanation
A Binary Search Tree is a tree where every node stores one value and has at most two children.
The rule is simple: everything on the left of a node is smaller than it, and everything on the right is bigger.
Because of this rule, searching feels like looking up a word in a dictionary — you keep cutting the remaining pages in half.
Key exam points
- In-order traversal of a BST yields sorted output
- All operations are O(h); balancing keeps h = O(log n)
- Deletion with two children uses the in-order successor
Previous year questions
Define a Binary Search Tree and write an algorithm to delete a node with two children.
2024 · 10 marks
Prove that in-order traversal of a BST produces keys in ascending order.
2023 · 6 marks
Compare AVL trees and Red-Black trees with respect to height and rotation cost.
2022 · 8 marks
Practice quiz
What is the worst-case time complexity of searching in an unbalanced BST?
Which traversal of a BST gives keys in sorted order?
When deleting a node with two children, it is replaced by its: