How Does Insertion Order Determine BST Shape?
A binary search tree preserves key order but not balance. Insertion order can produce a short tree or a linear spine.
A binary search tree invariant says that every left-subtree key is smaller and every right-subtree key is larger. It does not promise a balanced shape. Shape depends on insertion order.
Height recurrence
Let height(node) count real nodes on the longest downward path:
height(null) = 0height(node) = 1 + max(height(node.left), height(node.right))
This is a structural recurrence, not a calculation on key values. A leaf has height 1. A three-node right spine has height 3.
Press Run to execute this example. Use console.log to print a value.
The return invariant is that each call returns the height of exactly its subtree. The null base establishes zero; the recursive case adds the current node to the taller child path.
Search cost follows height
Search compares once per visited level, so it takes O(h) time. A balanced n-node BST has h = O(log n); sorted insertion into an ordinary BST can create h = n, making search O(n). Building by ordinary insertion can likewise range from O(n log n) to O(n²).
Edge cases and conventions
- Empty height is 0 when height counts nodes; an edge-counting convention would use -1.
- Do not sort the input before insertion: that changes the structure being measured.
- Decide where duplicate keys go, or reject them. The rule must stay consistent.
- Recursive height uses O(h) call-stack space and can overflow on a very long spine.
- Searching the original array bypasses the data structure and its shape.
Optional enrichment
Insert every permutation of [1, 2, 3] and group the resulting trees by height. Then compare with an AVL or red-black tree, which repairs height after updates.