Ordered, Unordered, and Binary Trees

Child Order Is Part of the Structure

A rooted tree has a distinguished vertex, the root, and its edges determine parent-child relationships as vertices get farther from the root. But a rooted tree alone does not say that one child comes before another, or that one child is on the left and another on the right. Those extra choices distinguish ordered rooted trees and binary trees from unordered rooted trees. Keeping the structures separate matters: two trees can have the same underlying graph and the same root, yet represent different ordered or binary trees.

Throughout, a tree is a finite, simple, connected graph with no cycles. A rooted tree is a tree with one specified vertex called its root. Each non-root vertex has a unique parent: the adjacent vertex on the path from it to the root. The children of a vertex are the vertices for which it is the parent. A rooted tree has at least one vertex; in particular, the tree consisting of a single root is allowed.

Definition: An unordered rooted tree is a rooted tree with no order specified among the children of any vertex. An ordered rooted tree is a rooted tree together with a linear order on the children of each vertex. An isomorphism of rooted trees must map root to root and preserve adjacency and parent-child relationships; for ordered rooted trees it must also preserve the order of the children at every vertex.

“Ordered” here refers to the children of each vertex, not to a numbering of all the vertices. The vertex names in an edge list are labels used to describe an example; they do not have to be preserved by an isomorphism. In an unordered rooted tree, exchanging two children and their descendant subtrees does not change the structure. In an ordered rooted tree, an isomorphism must send the first child to the first child, the second to the second, and so on.

Definition: A binary tree is a rooted tree in which each vertex has at most two children, with the child positions designated as left and right. A vertex with one child has that child in either the left position or the right position; the unused position is empty. A full binary tree is a binary tree in which every vertex has either zero children or exactly two children. A vertex with zero children is a leaf.

Thus a binary tree is not merely a graph whose vertex degrees are at most three. Its child counts are measured away from the root, and its left and right positions are part of the structure. A full binary tree has no vertex with exactly one child. A single root has zero children, so it is both binary and full under these definitions.

Recognizing Ordered and Unordered Isomorphisms

For a vertex \(v\), its rooted child-subtrees are the rooted trees consisting of each child of \(v\) together with all of that child's descendants. Removing the root of a rooted tree separates it into these child-subtrees. This gives a direct way to express what an isomorphism must do.

Proposition: Two finite rooted trees are isomorphic as unordered rooted trees if and only if their roots' child-subtrees can be paired so that each paired pair is isomorphic as rooted trees. They are isomorphic as ordered rooted trees if and only if the child-subtrees in each position are isomorphic as rooted trees.

Proof. Suppose first that an isomorphism maps one rooted tree to the other. It sends the root to the root and sends each child of the first root to a child of the second root. Since it preserves adjacency and the root, it maps the descendants of that child to the descendants of its image. Therefore it pairs the child-subtrees by rooted isomorphisms. If the trees are ordered and the isomorphism preserves child order, the child in each position must map to the child in that same position.

Conversely, suppose the child-subtrees can be paired by rooted isomorphisms. Map the first root to the second root, and on each child-subtree use its paired rooted isomorphism. The child-subtrees have disjoint vertex sets, and their only connection to the rest of the tree is through the root. Consequently these maps together define a bijection on all vertices that preserves adjacency and maps root to root. This is an unordered rooted isomorphism. If instead the child-subtrees are isomorphic position by position, use those isomorphisms in the corresponding positions. The resulting map also preserves child order, so it is an ordered rooted isomorphism. \(\square\)

For unordered trees the pairing may be chosen freely; for ordered trees the positions constrain it. In the binary setting the corresponding requirement is even more specific: the left child-subtree must match the left child-subtree, and the right must match the right. An empty position must match an empty position. This is why swapping left and right can change a binary tree even when the underlying rooted graph does not change.

Worked Classifications

Worked Example: Same Unordered Tree, Different Ordered Trees

Let both \(T\) and \(T'\) have vertex set \(V=\{r,a,b,c,d,e\}\), edge set \(E=\{ra,rb,ac,ad,be\}\), and root \(r\). In \(T\), order the root's children as \([a,b]\); in \(T'\), order them as \([b,a]\). At \(a\), the children are \(c,d\) in that order in both trees. All other vertices have no children.

Both trees are valid unordered rooted trees with the same root and edges, so the identity map is an unordered rooted isomorphism. To test ordered isomorphism, examine the first child of the root. An order-preserving isomorphism from \(T\) to \(T'\) would have to send \(a\), the first child in \(T\), to \(b\), the first child in \(T'\). But \(a\) has two children, while \(b\) has one. An isomorphism preserves the parent-child relation and hence the number of children, so no such map exists.

Check: The root has two children in each tree; the child-subtree rooted at \(a\) has two children at its root, and the one rooted at \(b\) has one. The unordered child-subtrees can be paired by matching the two-child subtree to itself and the one-child subtree to itself. They cannot be matched position by position under the specified root orders. Thus the trees are unordered-isomorphic but not ordered-isomorphic.

Worked Example: An Ordered Tree That Is Not Binary

Let \(T\) have vertex set \(V=\{r,a,b,c,d\}\), edge set \(E=\{ra,rb,rc,cd\}\), root \(r\), and root-child order \([a,b,c]\). The only child of \(c\) is \(d\); \(a,b,d\) have no children.

This is an ordered rooted tree: every vertex's children have a specified order (the lists with zero or one child require no choice between multiple children). It is not a binary tree under our definition because the root has three children, exceeding the maximum of two. It is therefore not a full binary tree either. Its root has three children even though its undirected degree is three; that degree happens to equal the child count at the root, but this coincidence does not make the allowed child count three.

Check: The parent-child lists are \(r:[a,b,c]\), \(a:[]\), \(b:[]\), \(c:[d]\), and \(d:[]\). The list lengths are \(3,0,0,1,0\), respectively. The root violates the binary bound, and \(c\) would also violate the full condition if the tree were binary, because it has exactly one child.

Worked Example: A Binary Tree That Is Not Full

Let \(T\) have vertex set \(V=\{r,a,b,c,d,e\}\), edge set \(E=\{ra,rb,ac,ad,be\}\), and root \(r\). Specify positions as follows: \(a\) is the left child of \(r\), \(b\) is its right child; \(c,d\) are the left and right children of \(a\); and \(e\) is the left child of \(b\). The right position at \(b\) is empty. Vertices \(c,d,e\) have no children.

Every vertex has at most two children, and every child that is present occupies one of the two designated positions. Thus \(T\) is binary. It is not full: \(b\) has exactly one child, and so does not have either zero or two children. The fact that \(b\)'s child occupies the left position does not change its child count.

Check: The child counts for \(r,a,b,c,d,e\), in that order, are \(2,2,1,0,0,0\). Each count is at most two, while the count \(1\) at \(b\) rules out fullness.

Worked Example: A Full Binary Tree and Its Positions

Let \(T\) have vertex set \(V=\{r,a,b,c,d,e,f\}\), edge set \(E=\{ra,rb,ac,ad,be,bf\}\), and root \(r\). Specify \(a,b\) as the left and right children of \(r\); \(c,d\) as the left and right children of \(a\); and \(e,f\) as the left and right children of \(b\). The vertices \(c,d,e,f\) have no children.

The root has two children, and each of \(a\) and \(b\) has two children. Each of \(c,d,e,f\) has zero children. Therefore every vertex has either zero or exactly two children, so this is a full binary tree and, in particular, a binary tree.

To see why positions matter, keep the same vertex set, edge set, and root, but exchange the left and right positions of \(a,b\) at \(r\), leaving all other positions unchanged. This gives another full binary tree. The identity map on vertices does not preserve the root's positions, so it is not a binary-tree isomorphism between these two specified structures. A different isomorphism might exist if the two child-subtrees match in a way that permits swapping them; the isomorphism test must check the structures of those subtrees as well as the positions.

Check: The child counts for \(r,a,b,c,d,e,f\) are \(2,2,2,0,0,0,0\). Each is either zero or two, and every vertex with two children has one in each position. This verifies both the full condition and the position requirements.

How the Definitions Fit Together

Every full binary tree is binary, because each of its vertices has either zero or two children, and both counts are at most two. The converse fails: a binary tree may have a vertex with exactly one child. Also, every ordered rooted tree is an unordered rooted tree after its child orders are forgotten, but retaining or changing those orders can affect ordered isomorphism.

Proposition: A rooted tree with designated left and right child positions is full binary if and only if each vertex has either both child positions occupied or neither position occupied.

Proof. Suppose the tree is full binary. At every vertex the number of children is zero or two. If it is zero, neither position is occupied. If it is two, there is at most one child in each of the two positions, so both positions are occupied. Conversely, suppose each vertex has either both positions occupied or neither occupied. A vertex with neither position occupied has zero children, and a vertex with both occupied has exactly two children, since each position holds at most one child. Thus every vertex has zero or exactly two children, which is the definition of full binary. \(\square\)

The proposition is a convenient classification test, but it depends on having a binary tree structure first: the two designated positions must be part of the data. An unordered rooted tree with two children at a vertex tells us that there are two children, but it does not by itself say which one is left and which one is right. Assigning positions equips it with binary-tree structure; different assignments need not describe isomorphic binary trees.

Common Mistakes and Why the Distinctions Matter

Mistake: using undirected degree to test the binary condition. For the tree with \(V=\{r,a,b,c,d\}\) and \(E=\{ra,rb,rc,cd\}\), the root has undirected degree \(3\). One might incorrectly argue, “The maximum degree is \(3\), so this is a binary tree.” That calculation tests the wrong condition. At the root, all three incident edges go to children, so the root has three children, not at most two. It is not binary. At a non-root vertex, undirected degree includes its parent as well as its children, so degree alone also does not give the child count.

Mistake: requiring every vertex of a full binary tree to have two children. This would wrongly exclude all leaves, including the four leaves in the full binary example. The correct requirement is zero or exactly two children. A vertex with one child makes a binary tree non-full; a vertex with three children makes it non-binary.

Mistake: treating child order as vertex labeling. An ordered rooted tree records the relative order among siblings, not fixed names for all vertices. An isomorphism can rename vertices, but it must carry each child position to the corresponding position. For unordered rooted trees, sibling order is not part of the structure at all. For binary trees, the left and right positions are specifically distinguished.

These distinctions are useful whenever rooted trees encode a hierarchy or a branching process. If siblings have a meaningful sequence, use an ordered rooted tree. If only the parent-child relationships matter, use an unordered rooted tree. If each vertex can have at most two designated branches, use a binary tree; if every non-leaf must use both branches, use a full binary tree.

Check Your Understanding

For each question, use child counts and positions rather than relying on a drawing.

Let \(V=\{r,a,b,c\}\), \(E=\{ra,rb,ac\}\), root \(r\), with \(a\) left of \(b\) at \(r\) and \(c\) the right child of \(a\). Is this tree binary? Is it full?
Can two rooted trees with the same root and edge set be isomorphic as unordered rooted trees but fail to be isomorphic as ordered rooted trees? Give an example and explain which child positions prevent an ordered isomorphism.
For a rooted tree whose root has three children and whose other vertices are leaves, which of the unordered, ordered, binary, and full binary descriptions apply if an order is specified on the three root children?
In a binary tree, what is the difference between a vertex with one left child and a vertex with one right child? When could the two resulting trees still be isomorphic?
Explain why an undirected degree of three at a non-root vertex does not by itself show that the vertex has two children.