liveBook · Manning

Full binary tree

As explained in Algorithms Every Programmer Should Know

A full binary tree is a binary tree in which every node has either zero children or exactly two children.

A full binary tree is a binary tree where every node has either no children or exactly two. A node with one child breaks the rule. Unlike a perfect binary tree, a full binary tree does not require all leaves to sit at the same depth. section 1.4.4

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 a full binary tree with ordinary and perfect binary trees. section 1.4.4

A reporting hierarchy

Imagine each manager reporting to either no one or exactly two managers. Individual contributors with no direct reports are leaves; a manager with only one direct report would violate the full-tree rule. section 1.4.4

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines the zero-or-two-child rule and distinguishes it from binary and perfect trees, without detailing construction.
Examples
Uses a reporting hierarchy and a diagram comparing binary, full, and perfect trees.
What you can do after
Evaluate whether each node in a binary tree has zero or exactly two children.
How it connects
Connects full binary trees to binary trees, perfect binary trees, leaf nodes, and BFS/DFS traversal.

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.