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