Binary Search Tree

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

Binary Search Tree Complete Implementation by SJ