liveBook · Manning

Binary tree

As explained in Algorithms Every Programmer Should Know

A binary tree is a tree in which each parent node has at most two child nodes.

A binary tree is a hierarchy in which each parent has at most two children, called the left and right nodes. Every node descends from a root; nodes with no children are leaves. section 1.4.4

Tree forms add different limits on how children and leaves are arranged:

  • A binary tree allows up to two children per parent. section 1.4.4
  • A full binary tree gives each node either zero or two children. section 1.4.4
  • A perfect binary tree has all leaves at the same depth. section 1.4.4

To explore a tree, breadth-first search (BFS) visits layer by layer, while depth-first search (DFS) follows a path toward a leaf before backtracking. A FIFO queue supports BFS; a LIFO stack supports DFS. Both take O(V) time, with space bounded by tree width for BFS and depth for DFS. section 1.4.4 section 1.5

Figure 1.8 A comparison of common binary tree structural variations. Left: A standard binary tree where nodes have a maximum of two children. Middle: A full binary tree enforcing that nodes possess either exactly zero or exactly two child nodes. Right: A highly uniform perfect binary tree where all interior nodes contain two children and every leaf node aligns at the exact same depth level.

Compare ordinary, full, and perfect binary tree shapes side by side. section 1.4.4

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines binary, full, and perfect trees; outlines BFS and DFS, including traversal time and space bounds.
Examples
Compares ordinary, full, and perfect tree shapes and contrasts layer-by-layer BFS with path-following DFS.
What you can do after
Understand how common tree forms differ and how BFS and DFS traverse them.
How it connects
Connects binary trees with breadth-first search, depth-first search, stacks, and queues.

Also explained in

Compare how 7 books explain binary tree →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.