> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-1/basic_data_structure/binary_tree/binary_search_tree.md).

# 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](http://algorithms.tutorialhorizon.com/binary-search-tree-complete-implementation/) by SJ