Binary Trees: Nodes With at Most Two Children

A binary tree is a set of nodes joined so that each node has at most two children, a left child and a right child, and every node but one has exactly one parent. This card covers the names for the parts of a binary tree, how depth and height are measured, and why a binary tree is a recursive structure.

A node holds a value and two links, one to its left child and one to its right, and either link may be empty, written null (None in Python). The root is the one node with no parent, drawn at the top. A node's parent is the node that links to it, and its children are the nodes it links to. A leaf is a node with no children, where a branch stops. An edge is one link from a parent to a child.

Depth and height are both counted in edges in this subject. A node's depth is the number of edges from the root down to it, so the root has depth 0. A node's height is the number of edges on the longest path from it down to a leaf, so every leaf has height 0, and the tree's height is the root's height. The tree below has seven nodes. Node 3 has only a right child, and its empty left link is drawn as null. Each note gives the depth and height that a short program printed for that node.

Every node is the root of a smaller binary tree, its subtree: the node and everything below it. Node 2's subtree holds 2, 4 and 5, and node 6's holds 6 and 7. That is what makes a binary tree a recursive structure. A binary tree is either empty, or a root with a left subtree and a right subtree, each of them a binary tree. The empty tree is the base case, the one answered without looking further, and most code for trees follows the definition: it does something at a node and asks each subtree for the rest.

A family tree drawn downwards from one ancestor gives the vocabulary: parent, child, and the generations as depth. The picture breaks on parents. Each person has two parents, so a real family tree branches upwards as well as downwards, while a node in a binary tree has exactly one parent, and only the root has none. That single parent is why there is exactly one path from the root to any node, and so one depth for every node.