Maintain an invariant for entire subtrees
In a binary search tree with distinct keys, every key in a node’s left subtree is smaller than the node’s key, and every key in its right subtree is larger. This condition applies to the whole subtree, not merely the immediate children. If the root contains eight, even a distant descendant on its left must remain below eight. Search uses this ordered separation to discard an entire subtree after each comparison. A design allowing duplicate keys needs an additional consistent rule for their placement or storage.
Trace a search and an ordered traversal
Insert 8, 3, 10, 1, 6, and 14 into an initially empty ordinary search tree. Looking for six follows 8 → 3 → 6: go left because six is below eight, then right because it exceeds three. If the required child does not exist before a match is found, the key is absent. Search time is O(h), where h is the tree height. Visiting the left subtree, then the node, then the right subtree produces keys in ascending order, which explains the structure’s usefulness for ordered queries.
Delete without breaking the key ranges
A leaf can be removed by clearing the incoming link. Deleting a node with two children is more involved because both subtrees must remain attached while preserving their ordering. One approach replaces its key with the minimum key from the right subtree and then removes that successor from its previous position. Choosing an arbitrary child as a replacement does not automatically preserve the ranges of all descendants. The necessary searches and rewiring still follow paths bounded by tree height, so describing deletion as O(h) makes the dependency explicit.
Do not assume a binary tree is balanced
Inserting 1, 2, 3, 4, and 5 into a naïve unbalanced search tree produces a chain extending to the right. Its height grows linearly with the number of keys, and lookup can consequently take O(n). Having at most two children does not imply logarithmic height. Balanced variants such as AVL and red-black trees perform structural repairs to control height and provide logarithmic worst-case basic operations. When choosing a tree for ordered iteration or range queries, identify the balancing guarantee of the actual implementation as well as its comparison and allocation costs.