Every Branch Has a Lineage

Find one route inside the tree

A single bright route stands out inside this branching tree. Follow it from the trunk to the selected outer branch. Other branches remain nearby, but they are not part of this route. Every branch has a particular history: the sequence of parents that led to it.

Select the neighboring outer branch. Most of the bright route stays the same, and only its final choice changes. These two branches share a parent. We can locate their relationship without counting every branch in the tree or measuring how far apart their endpoints are.

Return to the whole tree. A lineage is the chain of ancestors leading to one selected branch. The construction gives each non-root branch exactly one parent. That single-parent rule makes the route back to the trunk unambiguous, even when the drawing looks crowded.

Begin with the trunk alone emphasized. It is the root, so it has no parent in this tree. We will build an address by following child choices outward. The address describes the construction, rather than a screen position that would change if we moved the camera.

Build an address one choice at a time

Choose the left child of the trunk. Its lineage contains two segments: the original trunk and this child. Call the first choice left. The child belongs to generation one because we applied the branching rule once to reach it from the root.

At this child, choose its right child. We now have a two-choice address: left, then right. The highlighted route bends back toward the middle of the picture, but its first choice is still left. Read directions relative to each parent as the tree was constructed.

Choose left at the next fork. The full address is left, right, left. Three child choices identify a generation-three branch. Its lineage includes four segments because the original trunk comes before those three choices. Address length and lineage segment count differ by one.

Move closer to the selected final branch. This segment is one object, while its lineage is the longer chain leading to it. Keeping those meanings separate prevents a common counting error: selecting a generation-three branch does not mean that the highlighted chain contains only three segments.

Read relationships from shared beginnings

Pull back along the complete highlighted route. The address left, right, left leads to the branch we just visited. Its sibling has the same first two choices. We can locate that sibling by returning to the common parent and changing only the final choice.

Change the last choice to right. The new address is left, right, right. The trunk and the next two segments remain shared; the final segment is different. These branches are siblings because they have the same immediate parent, not merely because they appear close together.

Now select the branch reached by left, left, right. Its route separates from the previous route one step earlier. Both begin with the trunk’s left child, but their generation-two parents differ. Their shared ancestor is farther back than the parent they each touch directly.

Select a branch on the opposite main side, reached by right, left, left. Now only the trunk belongs to the beginning shared with the previous route. A longer shared address means a more recent shared ancestor. The first different choice tells us where the histories separate.

An ancestor is an initial part of the address

Return to the route left, right, left. Remove its final choice and you recover the address of its parent: left, right. Remove another choice and you reach the first-generation ancestor: left. Removing every choice leaves the root, whose address is empty.

Here is the parent, with address left, right. Its own lineage is shorter, but it lies completely inside the longer route we just followed. An ancestor’s address is an initial part of its descendant’s address. This gives us a precise rule for recognizing ancestry.

Now emphasize the ancestor reached by left. Every later branch whose address starts with left belongs below this ancestor. That collection forms a subtree. The current highlight shows the ancestor’s lineage, not every member of its descendant subtree; those are different collections.

Clear the highlight and inspect that left-hand region in context. A subtree contains a chosen branch and all its descendants. A lineage contains a chosen branch and its ancestors. One spreads outward; the other follows a single chain inward. Both are useful ways to read the same tree.

Addresses work beyond binary branching

Change to three children per parent and two repetitions. Each junction now offers left, middle, and right choices. The address needs three possible symbols at each step, but the idea is unchanged: record one choice per generation from the root to the selected branch.

Follow left, then middle. The selected second-generation branch continues along its parent’s direction. It can look like one long stroke, yet the construction contains two distinct segments after the trunk. Parent-child history remains meaningful when adjoining branches happen to line up.

Follow middle, then left instead. We used the same two words in the opposite order, and arrived at a different branch. An address is an ordered sequence, not an unordered collection of directions. The first choice establishes the parent on which the next choice acts.

Select right, then right. The route is now on the other side of the tree. Two decisions, with three options for each decision, give nine generation-two addresses. That is the same nine obtained by counting three children from each of the three first-generation parents.

A route is not a screen coordinate

Return to the binary route left, right, left. Its address names relationships: which child belongs to which parent. The picture also has lengths, angles, and screen positions, but those geometric quantities do not define the address. This distinction lets us reshape a tree without replacing its ancestry.

Compare the same address in a narrower tree. The branching angles are smaller, so the route occupies different positions, but it still makes the choices left, right, left. Its generation and parent chain remain unchanged. Geometry changed while the combinatorial relationship stayed fixed.

Compare a wider tree. The address and highlighted chain are again preserved. Some other branches may approach or cross in the drawing. A crossing away from a constructed junction does not create a new parent. Follow the actual branch connections rather than inventing connections at every visual crossing.

Restore the original angles and view the whole tree. Moving or zooming the camera would likewise change the image without changing a single parent-child relationship. An address remains a reliable identifier because it is tied to the construction rather than the viewport.

Use an address to compare two branching systems

Select the binary branch reached by left, then right, then left. Its address contains three choices, so it belongs to generation three. Follow the highlighted route from the trunk and count four segments. This separates the number of decisions from the number of objects visited along the route.

Visit the sibling reached by left, then right, then right. The two addresses agree in their first two choices and differ only in the third. Their common parent is therefore at generation two. The highlighted routes share the trunk and the next two segments, then separate at the final fork.

Now use three children at every fork and select the branch reached by the middle child followed by the first child. Its address has two choices and its lineage has three segments. The number of available child labels changed from two to three, but the relation between address length and generation did not change.

Move to the next sibling of that same ternary parent. The first choice remains the middle child; only the second choice changes. Read the shared prefix before looking at how near the branches appear on screen. Moving or turning the picture can change their apparent separation while preserving their ancestry.

Return to the complete ternary tree. Nine branches have two-choice addresses because each of three first choices has three continuations. The total is thirteen after adding the trunk and first generation. Addresses locate particular branches; summing across generations counts the complete construction. Keep both uses of the recursive rule available.

Find a branch deliberately

For a final prediction, start at the root and imagine right, then right, then left. Work outward one fork at a time. Do not choose a branch merely because its endpoint is somewhere on the right. The order of all three choices matters.

Here is the selected route. The first two choices took the right child twice; the final choice took the left child of that parent. Its three-letter address places it at generation three. Count the four highlighted segments, including the trunk, to check the lineage convention.

Choose Interact to select branches yourself. Keep Trace Lineage enabled, select a branch, and trace its bright route back to the trunk. Compare siblings, then compare branches on opposite sides. Resume returns to the lesson’s saved selection and view whenever you want to continue.

Return to the complete tree. A branch’s address records its choices, its lineage collects its ancestors, and its subtree collects its descendants. These ideas let us read an elaborate recursive picture as precise relationships. Next we will use those same routes to compare lengths that shrink at every generation.