Algorithms and data structures · Introductory

Binary search trees: height determines operation cost

Connect ordered subtrees, search paths, deletion, and the difference between balanced and unbalanced trees.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Maintain an invariant for entire subtrees
  2. Trace a search and an ordered traversal
  3. Delete without breaking the key ranges
  4. Do not assume a binary tree is balanced
  5. Ask Logeia about this articleCheck your understanding

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.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 9

Choose a learning path