Binary search tree

  • all items are stored in a binary tree
  • if \(v\) is a node with item \(x\), then all the smaller items are in the left subtree and all the larger items are in the right subtree
  • combines the advantages of sorted array (fast search) and linked list (flexibility when adding and deleting items)
  • all operations take \(O(h)\) time, where \(h\) is the height of the tree (usually small)
  • when the items are inserted in random order, the height is \(O(\log n)\) with high probability
  • all operations take \(O(h)\) time and \(h\) can be as large as \(n\)
[You can download the application for offline viewing.]

Exercise 1: Play around with the applet above. Try creating a binary search tree storing elements {1,2,3,$\ldots$,$n$} with the maximum height $n$How many different BSTs have height $n$?

Exercise 2: Now, try creating a BST storing {1,2,3,$\ldots$,$n$} with minimum height. How many such BSTs are there?

Exercise 3: How many different BSTs are there storing elements {1,2,3,$\ldots$,$n$}?

Tip: Type some number $n$ into the input box and press “Random” to insert random $n$ elements and observe the performance of the data structure on random data. What is the average height of the tree?

Exercise: Let’s take a BST, delete one of its elements and then reinsert it. When do we get the same BST with which we started?


  • A. Andersson. A note on searching in a binary search tree. Software: Practice and Experience, 21(10):1125-1128, 1991. [bib] [pdf]
  • Jeffrey L Eppinger. An empirical study of insertion and deletion in binary search trees. Communications of the ACM, 26(9):663-669, 1983. [bib] [pdf]
  • B. Reed. The height of a random binary search tree. Journal of the ACM, 50(3):306-332, 2003. [bib] [pdf]