Terminology

The root has no parent. Children belong below a parent; siblings share a parent. A leaf has no children. A node’s degree is its number of children. A subtree contains a selected node and its descendants. This material measures height in edges: a leaf has height 0.

Types

1. A binary tree has at most two ordered children per node.
2. A full or strict binary tree gives every node either zero or two children.
3. A complete binary tree fills every level except possibly the last, which is filled from left to right.
4. A perfect binary tree has all internal nodes with two children and all leaves at one level.
5. A skewed binary tree forms a one-sided chain.

Examples

A root with two leaf children is perfect, full and complete. A chain is still a binary tree but can have height n - 1. A binary tree is not automatically a binary search tree: the search-order rule must be separately maintained.

Counting and cost

A non-empty finite tree with n nodes has n - 1 parent-child edges. Traversing every node is O(n). Algorithms following a root-to-leaf path depend on height h, so the shape affects their work and recursive call depth.

Important convention

Some texts count height in nodes rather than edges. State the convention before using a numerical formula instead of treating two consistent conventions as contradictory.

Diagram or flowchart