Node, root, leaf and subtree

The basic vocabulary

A binary tree is a hierarchical data structure, made of nodes connected by parent/child links, where each node has at most two children: a left child and a right child.

• The node is the basic unit: it holds a value and up to two children.
• The root is the unique node with no parent, the one through which the whole tree is accessed.
• A leaf is a node that has no children.
• A subtree is simply the tree formed by a node and all its descendants; we speak of the left subtree and the right subtree.

Annotated diagram

              5              (root, no parent)
            /   \
           3     8           (3 and 8 are children of 5)
          / \     \
         1   4     9         (1, 4 and 9 are leaves: no children)

left subtree of 5  : the node 3 and everything it contains (3, 1, 4)
right subtree of 5 : the node 8 and everything it contains (8, 9)

Parent and depth

Every node, except the root, has exactly one parent. The depth of a node is the number of links to travel from the root to reach it: the root is at depth 0, its direct children at depth 1, and so on.

Common pitfall

Do not confuse "leaf" and "empty subtree": a leaf is a real node, with a value, that simply has no children. An empty subtree (often written None in Python) means the complete absence of a node at that spot. Many tree algorithms stop precisely when they reach an empty subtree, which marks the end of a branch.