Binary tree

As explained in Learn C++ by Example

A binary tree is a tree data structure in which each node has at most two child branches.

A binary tree stores elements in nodes, with each node pointing to at most two child nodes. A binary search tree orders smaller elements to the left and larger elements to the right. section 7.2.1

The C++ map uses a binary search tree to store key-value pairs. The key determines whether each pair moves left or right, making searches faster than scanning every element in a vector. section 7.2.1

Following a search

Insert {1:a}, {3:c}, and {5:e}. The tree is reorganized so {3:c} becomes the top node, with {1:a} on the left and {5:e} on the right. Searching for {2:b} compares against 3, moves left to 1, and stops at that leaf. section 7.2.1

Figure 7.2 Three elements in a balanced binary search tree: nodes with smaller keys go on the left and larger keys on the right.

Use the balanced-tree figure to see how key ordering places smaller nodes left and larger nodes right. section 7.2.1

How Learn C++ by Example covers it

How deep it goes

Explains nodes, child pointers, ordering, balancing, and one search path, but stops short of implementation code.

Examples

Uses map pairs {1:a}, {3:c}, and {5:e}, plus a search for {2:b}, to demonstrate insertion and traversal.

What it assumes

Assumes familiarity with vectors, arrays, and map key-value pairs while introducing nodes, child pointers, leaves, and ordering.

What you can do after

Evaluate how map ordering and balancing reduce search work compared with linear container scans.

How it connects

Connects binary trees with maps, vectors, arrays, binary search trees, keys, values, and time complexity.

liveBookmanning.com

Read Learn C++ by Example on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Grokking Machine LearningA tree data structure in which each node has at most two child branches.
• 

  liveBookmanning.com
  Grokking Algorithms, Second EditionA binary tree is a tree in which each node has at most two children.
• 

  liveBookmanning.com
  Machine Learning for Tabular Data: XGBoost, Deep Learning, and AIA tree data structure in which each node has at most two child nodes.

Compare how 4 books explain binary tree →

Related concepts

• treekind of · A tree is a connected, acyclic structure of nodes, commonly organized hierarchically through parent-child relationships and optionally around a designated root.
• binary search treeincludes · 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.
• heapincludes · A binary heap is an almost complete binary tree in which each parent satisfies an ordering property relative to its children, enabling efficient access to a minimum or maximum element.
• k-d treeincludes · A k-d tree is a binary space-partitioning tree that organizes points in multidimensional space by recursively comparing coordinate dimensions.
• subtreeincludes · A subtree is a tree formed by a node and all its descendants, together with the links connecting them.
• Mapcontrasts with · A map is an associative data structure that stores key-value pairs and supports retrieving values by key.

This explainer was generated by Manning's knowledge graph from the text of Learn C++ by Example. The section links point to the parts of the book it draws on.