# Binary Search Trees

Binary Search Trees are the first of many specialized trees

Binary search trees have the core property where `left <= node < right`

thus allowing elements to be stored in sorted fashion easily

## Runtime analysis

BSTs have the same runtime as Trees but if the tree is balanced, it implies that insertions of elements in sorted order can be done in $O(\log n)$ which is faster than what inserting into a sorted array can achieve

## Core properties

`left <= node < right`

In-order traversal produces a sorted array

The maximum value exists on the rightmost leaf of the right sub-tree

The minimum value exists on the leftmost leaf of the left sub-tree

## Techniques

Most of the techniques of a BST is the same as those Trees, however, there is a technique that only BSTs can achieve

### Using in-order traversal

The core property of BSTs allow in-order traversal to become a sequential traversal of the elements in sorted order. Once a problem mentions that the tree is a BST, try thinking of how to exploit this property to solve the problem

Last updated