Binary Search Trees

Notes for a lecture I gave as an undergrad

Published

19 November 2019

I’m publishing this in 2025, with some added context, and hence the use of past tense.

Notes for a lecture I gave at IIT Roorkee on Binary Search Trees. After motivating the need for the data structure using a runway reservation system problem, I introduce tree terminology and the basic operations on a binary search tree. Also discussed are the ordering invariant and rounding-up with minor algorithms and runtime technicalities.

Citation

@article{kilaru2019bstlecture,
  title   = "Lecture: Binary Search Trees",
  author  = "Kilaru, Yasaswi Sri Chandra Gandhi",
  journal = "kyscg.github.io",
  year    = "2019",
  month   = "Nov",
  url     = "https://kyscg.github.io/2019/11/19/bstlecture/"
}