Count distinct labels by checking constructor assumptions

Try

A tree diagram can contain five vertices while using only three names. Suppose a folder tree repeats the name “draft” in different places. Counting visible positions answers a different question from counting distinct names. We will make that distinction precise before attempting an induction proof.

Our objects are finite ordered full binary trees. A tree is either Leaf(a), one vertex labeled a, or Node(a,L,R), a new vertex labeled a with left child tree L and right child tree R. Every internal vertex has exactly two children. Labels may repeat unless a rule explicitly forbids that. These are constructor trees, not graphs with shared vertices: inserting the same child expression twice creates two occurrences.

Write v(T) for the number of vertex occurrences and S(T) for the set of labels appearing. A set records each name once. Build Node(a,Node(b,Leaf(a),Leaf(c)),Leaf(b)) on paper. Count positions first; then cross out repeated names in your list.

Predict

Predict whether the equation “parent label count = one plus both child label counts” is always correct. Name two different reasons it might overcount. Is checking only that the root has a new name enough? Is checking only that the two children use different names enough?

Keep your predictions: the diagram deliberately violates both proposed shortcuts at its outer root. Neither violation changes the number of positions in the tree.

Experiment

Subtree	Vertex occurrences v	Label set S	Distinct labels
Left child	3	a, b, c	3
Right child	1	b	1
Whole tree	5	a, b, c	3

The naïve addition gives 1+3+1=5. First, b appears in both child sets, so their union has 3+1−1=3 labels. Second, the root a already belongs to that union, so adding the root contributes zero new labels. The correct total remains three.

Now relabel the right leaf d and the root e, leaving the left subtree unchanged. Recompute every row. The whole tree now has five distinct labels: the children have disjoint sets and the root is fresh. This is a change to labels, not to shape or occurrence count.

Understand

Define admissible recursively. Every Leaf(a) is admissible. Node(a,L,R) is admissible if both children are admissible, their label sets are disjoint, and a belongs to neither child set. “Disjoint” means their intersection is empty; “fresh” means absent from the union. The recursive child condition prevents repetitions hidden deeper in a subtree.

Prove that every admissible tree satisfies |S(T)|=v(T). The leaf case is one label and one vertex. At a node, assume the result for both children. Child disjointness lets us add their set sizes; root freshness contributes exactly one. Therefore |S(T)|=1+|S(L)|+|S(R)|=1+v(L)+v(R)=v(T). Each equality has a reason. Structural induction supplies the child equalities; it does not supply disjointness or freshness unless the constructor includes them.

There is also an exact formula without these restrictions. Let j be the number of labels shared by the children, and let e be 1 when the root label already occurs in a child, otherwise 0. Then

|S(T)| = |S(L)| + |S(R)| − j + 1 − e.

This is inclusion-exclusion followed by the root contribution. Define the deficit d(T)=v(T)−|S(T)|. Subtraction yields d(T)=d(L)+d(R)+j+e. All terms are nonnegative integers. Consequently a parent has deficit zero exactly when both children have zero deficit, j=0 and e=0. This proves a converse too: our recursive rules describe precisely the trees whose vertex labels are all distinct.

The familiar full-tree identity v=2i+1, where i counts internal vertices, needs no uniqueness of labels. Its induction uses occurrences only. Do not transfer that identity to label-set cardinality without proving the additional conditions.

Apply

Use the changed tree Node(r,Node(s,Leaf(t),Leaf(t)),Leaf(u)), with r,s,t,u different. The outer root is fresh and the outer child sets are disjoint. Predict whether those two facts certify five distinct labels. Locate the missing constructor obligation and compute the deficit from the recurrence before opening the feedback.

Check the changed case

The left child has three occurrences but only two labels, so its deficit is one. The right child has deficit zero, and the outer j and e are zero. The whole deficit is therefore one: five vertices use four labels. The left child violates disjointness between its two leaves. Conditions at the outer root alone cannot justify an induction hypothesis about an invalid child.

For a further repair, replace only one repeated t by v, a label absent from the tree. Explain why all constructor conditions now hold. Then replace r by s instead: explain why the newly valid children do not rescue the root-freshness failure.

Continue

Return to recursive tree proofs if you need practice stating both child hypotheses. In the written tasks, identify the counted object before manipulating a recurrence: positions, distinct labels and leaves are different sets. Supply counterexamples as well as repaired general proofs. A successful calculation on this five-vertex diagram supports understanding of the definitions; the induction argument is what establishes the claim for every finite admissible tree.