Data structure & algorithms (Binary Search Tree (BST)notes)

Data Structures and Algorithm
(CC-2042)
Lecture 23
E N G R. D R B I L A L A S H FA Q A H M E D
S C H O O L O F S Y S T E M S A N D T E C H N O LO GY ( S S T )
C O M P U T E R S C I E N C E FA C U LT Y

, Binary Search
Tree (BST)
 A Binary Search Tree (BST) is a
specialized binary tree where:
1. Each node has at most two chil
left and right.
2. The left subtree of a node cont
nodes with values less than the
node’s value.
3. The right subtree of a node con
nodes with values greater than
node’s value.
4. Both left and right subtrees are
BSTs.




09/06/2025 DS

, Applications of Binary Search
Tree (BST):
 A Self-Balancing Binary Search Tree is used to maintain sorted stream of data.
 A Self-Balancing Binary Search Tree is used to implement doubly ended priorit
queue.
 There are many more algorithm problems where a Self-Balancing BST is the b
suited data structure, like count smaller elements on right, Smallest Greater
Element on Right Side, etc.
 A BST can be used to sort a large dataset. By inserting the elements of the
dataset into a BST and then performing an in-order traversal, the elements wi
be returned in sorted order.
 Variations of BST like B Tree and B+ Tree are used in Database indexing.
 TreeMap and TreeSet in Java, and set and map in C++ are internally
implemented using self-balancing BSTs, more formally a Red-Black Tree.



09/06/2025 DS