Constructors and tree invariants

Try

Build a tree before counting it.

Draw a single dot and call that object Leaf. Now take two separately drawn trees S and T, add a new dot above them, and connect that dot to their roots. Put S on the left and T on the right. Call the result Node(S,T). Repeating these instructions finitely many times builds the objects in this lesson: finite ordered full binary trees.

“Full” means that every nonleaf vertex has exactly two children. It does not mean that all leaves are at the same depth. “Ordered” means that left and right are part of the structure. A vertex with one child is not permitted here. Nor is an infinite construction. There are no additional trees beyond those produced by the two rules.

Build A=Node(Leaf,Leaf). Next build W=Node(Leaf,A), using a new copy of A. Count the dots with no children and the dots with children separately. A leaf count L records the first kind; an internal count I records the second. These are counts of vertex occurrences, not counts of distinct names in a formula.

Predict

What does one constructor change?.

The single Leaf has L=1 and I=0. If two already-built trees have leaf counts 2 and 3, predict the leaf count after joining them under a new root. Does that new root count as a leaf? Does either old root disappear?

The answer is five leaves. Both old trees remain, and the new root is internal, so its internal count is one plus the two old internal counts. Predict the value of L−I for W. Then construct a taller, unbalanced example before deciding what might hold for every permitted tree. Several matching examples can suggest an invariant—a quantity that stays the same under the constructor—but cannot prove it for every size.

Experiment

Compute from the leaves upward.

Cover the root’s label and calculate it from its children. Use the following recursive definitions; the semicolon separates two counts, not two competing choices.

Constructor	Leaf count L	Internal count I
Leaf	1	0
Node(S,T)	L(S)+L(T)	1+I(S)+I(T)

For A, these clauses give L(A)=1+1=2 and I(A)=1+0+0=1. For W they give L(W)=1+2=3 and I(W)=1+0+1=2. Draw Node(A,Leaf) beside W. Its counts match, but its left/right structure differs: equal totals do not identify a tree.

Now replace W’s left leaf by a copy of A. Mark exactly which leaf was removed and which vertices were added. Predict the new counts before reading the feedback.

Check the changed construction

The result is Node(A,A), with two separate copies of A. It has four leaves and three internal vertices. Replacing one leaf by A changes L by −1+2=1 and I by 1. Sharing one drawn copy of A between two parents would create a different kind of object; it is not this constructor tree.

Understand

A proof follows every constructor.

The claim is L(U)=I(U)+1 for every finite ordered full binary tree U. Read it as “every permitted tree has one more leaf than internal vertices.” The formula describes counts, not an empirical trend.

Base constructor. For U=Leaf, the definition gives L(U)=1 and I(U)=0, so the claim is true.

Joining constructor. Take arbitrary permitted trees S and T. Assume the claim holds for each child: L(S)=I(S)+1 and L(T)=I(T)+1. These are two hypotheses, not an assumption that the new parent already satisfies the claim. The recursive clauses give

L(Node(S,T)) = L(S)+L(T) = I(S)+1+I(T)+1 = I(S)+I(T)+2.

Meanwhile I(Node(S,T))+1 = [1+I(S)+I(T)]+1 = I(S)+I(T)+2. The expressions agree, proving preservation by Node. No equal-height or equal-size assumption was used.

Why do these cases reach every tree? Every allowed object has a finite construction. Its terminal pieces are Leaves; each application of Node combines two previously constructed objects. Following that construction from its terminal pieces to its root propagates the proved property all the way. Formally, one can justify this by strong induction on the finite number of vertices: both children have fewer vertices than their new parent. This explains the structural-induction principle without assuming the particular count identity we are trying to prove.

The same finite descent justifies recursive evaluation of L and I. Every recursive request concerns a proper child, and eventually reaches Leaf. A definition that called L on its unchanged parent would not have this justification. The unique outer constructor and ordered children specify which clause to use; the grammar is not merely a suggestive sketch.

Invalid proof diagnosis. Suppose someone checks Leaf and Node(Leaf,Leaf), then says “larger trees work the same way.” They have not shown preservation when the children themselves have arbitrary structure. Another proof might join only two identical children. That covers balanced constructions of a special form and omits Node(Leaf,A). Repair either proof by stating both arbitrary child hypotheses and doing the constructor arithmetic above. An omitted case can invalidate an argument even when its conclusion happens to be true.

Apply

Preserve the domain as you change the object.

Write a fresh proof of E(U)=2I(U), where E counts edges. Start with E(Leaf)=0. Explain why joining S and T adds exactly two edges, and why the internal count adds exactly one vertex. The practice tasks ask you to connect this result to the total vertex count without assuming a graph-theory theorem.

Then change the rules: permit a root with just one child. Draw the new object One(Leaf). It has one leaf and one internal vertex, so L=I+1 fails. The old proof has no One case, and that missing case cannot be repaired while keeping the same claim. Distinguish this situation from an incomplete proof of a true statement: the enlarged-domain statement itself is false.

Finally write what evidence your original drawings supply. They check arithmetic and clarify the rules. They do not establish the universal constructor step. A convincing written response should identify the domain, state every base case, quantify the arbitrary children, use the correct recursive clauses and explain why these cases exhaust all finite constructions. The rubric is a guide for a human reader, not an automatic proof checker.

Continue

Carry a structural proof, not a picture pattern.

Save the constructor definitions alongside your argument. In the six tasks, you will audit a larger tree, prove an edge invariant, repair a one-sided constructor step, challenge a changed domain, replace a leaf and combine trees into a forest. The objects change, so decide what must be counted and which constructor hypotheses are available each time.

For a recap, revisit ordinary and strong induction and double inclusion for sets. Later work can apply the same method to strings and expression trees, but those additional constructors require their own definitions and cases. Checking this one tree identity does not certify every structural-induction argument.