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

Core properties

  1. left <= node < right

  2. In-order traversal produces a sorted array

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

  4. 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