Lesson 14 — Binary search tree: insert

Binary search tree: always ordered

A binary search tree (BST) is a binary tree with a rule: everything in a node's left subtree is smaller, everything in the right is bigger or equal. To insert, start at the root and go left or right until you find an empty spot. Because of the rule, an in-order walk (left, node, right) visits values in sorted order.

#     5
#    / #   3   7    in-order: 3, 5, 7

Why it matters: search, insert and delete take O(log n) on a balanced BST — this is how many databases keep data sorted.