Binary Search Tree: Insert and Search

A tree that keeps numbers organized so you can find any of them by going left or right.

The idea (a sorted phone book as a tree)

A binary search tree (BST) follows one rule at every node: everything in the left subtree is smaller, everything in the right subtree is bigger. That is binary search turned into a shape: at each node you ask “is my number smaller or bigger?” and throw away half of what is left.

If the tree stays balanced, each step halves the problem, so lookups are fast. But the insert order matters: try inserting already-sorted numbers and see what happens to the shape.

Watch it work

Try it

Common mistakes

Complexity, in plain English: a search or insert follows one path from the root, so it costs about the height of the tree. A balanced tree with 1,000,000 values has height about 20 (O(log n)); a stick-shaped tree has height n (O(n)).