Binary Search Tree (BST)
Definition
A BST is a binary tree where each node has 3 fields (key, leftChild, rightChild).
- leftChild and rightChild are also BSTs
- N.key > any keys in N.leftChild
- N.key < any keys in N.rightChild
BST Operations
- Insert - easy
- Search - easy
- Delete - careful
- search(k) first, then we have 3 cases
- if k is a leaf just delete it
- if k has one child, then replace k with its child
- if k has two children, replace k with the largest node in k.leftChild or the smallest node in k.rightChild, then recursively delete the replacing node
- Range query
Approach
How do you solve BST questions using its special property sorted?
References
UMD CS420 Data Structures by V.S. Subrahmanian