Binary search trees

A binary search tree adds one rule to a binary tree. Every value in the left subtree is smaller than the node, and every value in the right subtree is larger. Duplicates are a policy decision. This course does not insert them.

Search starts at the root. A smaller target goes left. A larger target goes right. Null means the value is absent. The walk takes time proportional to the height, not automatically to log n. A balanced tree has height about log n. Inserting already-sorted values in order produces a straight line, and search falls back to O(n). The tree did not save you.

Insert uses the same walk. The empty spot on the correct side is where the new node goes. Scanning the original array with a linear search misses the point of building the tree. The structure only helps if the lookup follows the left-and-right rule.