Binary search tree

As explained in 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.

A binary search tree (BST) is a binary tree whose nodes follow an ordering rule: every value in a node’s left subtree is smaller, and every value in its right subtree is larger. Each node has at most two children. section 8.2

Searching for a value

To find 7 in a tree rooted at 10, compare 7 with 10 and move left. At 5, compare again and move right to find 7. To search for 8, follow the same path; the missing value would occupy the next appropriate position. Each comparison discards an entire subtree. section 8.2

A BST combines the fast searching associated with sorted data and the flexible insertion associated with linked structures. Its performance depends on height: a short tree supports O(log n) searches, while repeatedly inserting larger values can produce a one-sided tree with height O(n). section 8.2 section 8.3

Use the tree diagrams to trace comparisons, subtree choices, and the path taken during a search. section 8.2

Balancing keeps the height near O(log n). AVL trees are self-balancing BSTs that update heights and balance factors after insertion, then use rotations when necessary; they provide O(log n) searches and insertions. section 8.6

How Grokking Algorithms, Second Edition covers it

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 it assumes

Assumes familiarity with basic trees and contrasts their performance with arrays and linked lists.

What you can do after

Evaluate BST search and insertion trade-offs and understand how AVL balancing preserves logarithmic performance.

How it connects

Connects binary trees with sorted arrays, linked lists, tree height, balanced trees, AVL trees, and rotations.

liveBookmanning.com

Read Grokking Algorithms, Second Edition on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Grokking Data StructuresA 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.
• 

  liveBookmanning.com
  Advanced Algorithms and Data StructuresA binary search tree is a binary tree organized by an ordering relation that places smaller and larger keys in designated subtrees.
• 

  liveBookmanning.com
  LatencyA binary search tree is an ordered tree data structure in which values in each subtree follow a binary-search ordering relative to its node.
• 

  liveBookmanning.com
  Learn C++ by ExampleA 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.

Compare how 5 books explain binary search tree →

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.

This explainer was generated by Manning's knowledge graph from the text of Grokking Algorithms, Second Edition. The section links point to the parts of the book it draws on.