Binary search tree visualiser

What makes a binary tree a binary search tree

The figure above draws binary search trees, which are a narrower thing than binary trees. A binary tree is only a shape: every node has at most two children, and nothing says which value belongs where. A binary search tree keeps that shape and adds one rule — at every node, every value in the left subtree is smaller than the node and every value in the right subtree is larger.

Read the tree this page starts from — Reset restores it — beginning at its root, 50. The three values to its left, 20, 30 and 40, are all smaller than 50; the three to its right, 60, 70 and 80, are all larger. The same holds one level down at 30 and at 70, and it has to hold at every node, not only the root. A tree where it fails somewhere is still a binary tree, just no longer searchable — and the Insert control here cannot build one, because it places each value by that same comparison.

That rule is what turns a search into a walk downwards. Looking for 40 in that tree: compare it with 50 and go left, compare it with 30 and go right, and there it is — three comparisons, the first two of which ruled out a whole branch rather than a single value. What the rule does not decide is which value ends up at the root, so the same seven numbers inserted in another order build a different shape, and the comparison count follows the shape. That is what the controls above are for.