What is a binary tree, and what is a proper binary tree?
A binary tree is a tree in which every node has at most two children, and the children form an ordered pair: a left child and a right child. In a proper binary tree every internal node has exactly two children.
Two properties define a binary tree:
- At most two children per node.
- The children are ordered as left and right. A node with only one child still has to say which one it is. A node with just a left child and a node with just a right child are two different binary trees.
There is also an equivalent recursive definition: a binary tree is either
- empty or a single node, or
- a root whose children are an ordered pair (left, right) of binary trees.
That recursive form is why so many binary-tree algorithms have the same shape: handle the node, recurse left, recurse right.
A proper (or "full") binary tree tightens rule 1 to exactly two children for every internal node, so no node has just one child. Expression trees are proper: every operator has exactly two operands.
Applications: arithmetic expressions (operators with two operands), decision processes (yes/no questions), and searching (smaller keys left, larger keys right).
Go deeper:
Binary tree — the types (full, complete, perfect), their properties, and array and linked storage.
MIT 6.006 — Binary Trees, Part 1 — traversal order, height and the operations on binary trees.