Binary Search Trees
The binary search tree is a linked structure that incorporates the binary search strategy. Each node in the tree contains an item and two pointers to other nodes, called child nodes. Figure 17.12 shows how the nodes in a binary search tree are linked. The idea is that each node has two child nodes, a left node and a right node. The ordering comes from the fact that the item in a left node precedes the item in the parent node, and the item in the right node follows the item in the parent node. This relationship holds for every node with children. Furthermore, all items that can trace their ancestry back to a left node of a parent contain items that precede the parent item in order, and every item descended from the right node ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access