Binary search tree
A binary search tree is a binary tree whose nodes follow an ordering relation placing keys in designated left and right subtrees relative to each node.
Grokking Data Structures
A binary search tree is a binary tree whose node values obey an ordering rule in which left-subtree values are less than or equal to a node value and right-subtree values are greater.
- How it is used
- Organizes values for searching while allowing insertion and deletion without maintaining a sorted array.
- How deep it goes
- Defines ordering and works through core operations and height costs; points to balanced variants rather than implementing them.
- Examples
- Uses a card-finding challenge, duplicate insertion, and sorted insertion sequences that produce skewed trees.
- What you can do after
- Build it from scratch with Python nodes and core methods, and evaluate how tree height affects their performance.
Read how Grokking Data Structures explains binary search tree →
Advanced Algorithms and Data Structures
A binary search tree is a binary tree organized by an ordering relation that places smaller and larger keys in designated subtrees.
- How it is used
- Supports dictionaries and ordered searches where predecessor, successor, minimum, maximum, or sorted output matter.
- How deep it goes
- Defines ordering, explains insertion and height-based complexity, and applies balanced trees to nearest-neighbor search.
- Examples
- Uses cities and warehouses, coordinate 75, ordered insertions, and comparisons with hash tables.
- What you can do after
- Evaluate/understand when balanced BSTs outperform linear structures for ordered lookup and nearest-neighbor tasks.
Read how Advanced Algorithms and Data Structures explains binary search tree →
Grokking Algorithms, Second Edition
A binary search tree is a binary tree whose nodes are ordered so that values in the left subtree precede the node's value and values in the right subtree follow it.
- How it is used
- Uses ordered tree structure to provide fast searches while retaining faster insertion than sorted arrays.
- How deep it goes
- Explains node ordering, search paths, height-based performance, and the need for balancing, but defers most AVL rotation cases.
- Examples
- Uses a tree containing 10, 5, and 20 to trace searches for 7 and 8, then shows a one-sided tree formed by increasing insertions.
- What you can do after
- Evaluate BST search and insertion trade-offs and understand how AVL balancing preserves logarithmic performance.
Read how Grokking Algorithms, Second Edition explains binary search tree →
Latency
A binary search tree is an ordered tree data structure in which values in each subtree follow a binary-search ordering relative to its node.
- How it is used
- Guides data-structure choice in latency-sensitive code where ordered values and growing-input latency matter.
- How deep it goes
- Compares average and worst-case operation costs but stops short of explaining tree operations or implementation details.
- Examples
- Uses range-valued search and a comparison table covering common data structures.
- What you can do after
- Evaluate data structures by comparing average and worst-case complexity against ordering requirements.
Learn C++ by Example
A binary search tree is a binary tree whose nodes are ordered so smaller elements lie to the left and larger elements lie to the right.
- How it is used
- Explains how map storage supports faster searching than scanning every element in a vector.
- How deep it goes
- Defines nodes, branches, ordering, balancing, and logarithmic operations through a small map example.
- Examples
- Uses map pairs {1:a}, {3:c}, and {5:e}, then traces a search for {2:b}.
- What you can do after
- Understand why balanced ordered storage reduces map search, insertion, and removal from linear to logarithmic complexity.
Related concepts
- binary treekind of · A binary tree is a tree data structure in which each node has at most two children.
- self-balancing binary search treeincludes · A self-balancing binary search tree automatically maintains bounded, typically logarithmic height as elements are inserted or removed.
- k-d treeincludes · A k-d tree is a binary space-partitioning tree that organizes points in multidimensional space by recursively comparing coordinate dimensions.
- subtreehas part · A subtree is a tree formed by a node and all its descendants, together with the links connecting them.
- Mapimplements · A map is an associative data structure that stores key-value pairs and supports retrieving values by key.
- similarity searchuses · Similarity search is a retrieval technique that finds or ranks items by comparing their representations with a query according to a similarity or distance measure.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.