Binary Search Trees & AVL Trees

A binary search tree (BST) keeps its values ordered: for every node,

• every value in the left subtree is smaller, and • every value in the right subtree is larger.

That single rule makes searching fast — at each node, compare and go left or right, discarding half the remaining tree, just like binary search on an array.

An in-order traversal of a BST lists its values in sorted order.