> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook/17.-b-trees/17.1-bst-performance.md).

# 17.1 BST Performance

## Tree Height

One unforunate feature of BSTs is that they range from a best-case "bushy" tree to a worst-case "spindly" tree. 

In the best case, our tree will have height $$\Theta(log N)$$, whereas in the worst case our tree has a height of $$\Theta(N)$$, at which point it basically becomes a linked list. For example, `contains` on a "spindly" BST would take linear time.

Both trees below have a height H = 3, yet the left tree is able to hold many more items than the left.

<figure><img src="https://2316889115-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FCLYj7ccqvV6l4Pt9R0w5%2Fuploads%2F7PJe5K8xiYxZ0HCTrjuh%2Fimage.png?alt=media&amp;token=60c8be95-f3d4-4fd9-9f02-0e4375a31853" alt=""><figcaption></figcaption></figure>