# Math 188 - Winter 2001 - Prof. TeslerMajority Tree

Links:     Description     Animation instructions     Animation     Math 188 home

Consider a tree of depth d in which all internal nodes have three children, and all leaves are on level d. At every leaf, we assign a value 0 or 1.  At every internal node, the value 0 or 1 is computed by taking the majority of the values at its three children (if two or three children have value x, the node is assigned x too). Here is such a tree with d=2:

We want to find the value assigned to the root.  An upper bound on the number of leaves that we have to examine to compute this is 3d (that is, all of them).  However, if we are lucky, we may be able to examine fewer: if in any group of three sibling nodes, the first two examined have the same value, that value propagates up to the parent, and there is no need to look at the third node or any of its descendants; they are rendered irrelevant.

For example, in the tree shown above, if we read the leaves from left to right, skipping irrelevant ones, then we would first examine leaf [1]

and leaf [2]

In their group of siblings [1-3], they give two 0's, so there is no need to examine leaf [3]; we just propagate the value 0 up a level, and mark [3] as "irrelevant" with an "X." Then we examine leaf [4]

and leaf [5]

and still do not have a majority in the sibling group [4-6]. We read leaf [6]

and the majority value of leaves [4-6] is 0, so we set their parent to 0. This makes two of the siblings on level 1 have value 0, so the root has value 0 too; there is no need to examine the third node on level 1, or its children [7-9], so mark them irrelevant. Examining the leaves in this order required seeing the values of 5 leaves.

If instead of reading the leaves left to right, we chose the order by some other rule, and we happened to start out [1] [2] [4] [6], we would know the value of the root is 0 after examining just 4 leaves.

We can turn this into a 2-player (mathematical) game.  For each round of play,

• The Solver chooses a leaf whose value has not yet been assigned.  A wise solver will skip leaves whose values are irrelevant.
• The Opponent determines the value (0 or 1) to assign to that leaf.  If all the values were chosen beforehand, the opponent would simply read off the preassigned value; however, by formulating it as a game, we can develop strategies for the opponent to choose the value 0 or 1 on-the-fly to construct best and worst case inputs for the solver.
• If it's possible to determine the value of the leaf's parent or other ancestors, the solver should do so. If any of these newly evaluated nodes have descendants whose values have not yet been determined, they should be marked as irrelevant.

Then play another round.  Eventually, the value of the root will be determined.

The applet below demonstrates this game.

Here are some questions about how many leaves the solver must examine. See the problem set and solutions.

• What is the minimum number of leaves the solver could conceivably examine?
• What is the average number of leaves the solver will examine by reading them from left to right, skipping over ones that are unnecessary because their ancestor's values are already known?  The average is taken over all 23d settings of the leaves.
• Prove that all valid strategies for reading the leaves have a worst-case requiring them to read all 3d leaves.  This can be done with an adversary argument, based on the game formulation described above.

# Instructions

The applet below has several strategies for the two players:

• The Solver may choose leaves
• Sequentially from left to right, skipping over any that are irrelevant because the values of prior leaves already imply the value of an ancestor of this leaf;
• Randomly; the leaves will be chosen in a random order, but irrelevant leaves will be skipped.
• The Opponent may be
• a Friend who always returns 0, or who always returns 1;
• a Random opponent who flips a coin to pick 0 or 1;
• an Adversary whose goal is to make the solver read as many leaves as possible.  If one value (0 or 1) will create a majority and the other will not, it chooses the one that will not.  Otherwise, the normal adversary picks 0 for the first node in a group of 3 siblings, and 1 for the second, while the random adversary picks 0 or 1 randomly.
• You may click on the last assigned leaf (shown in bold) or any unassigned leaf marked "?" (irrelevant ones marked "X" are not allowed) to change its value manually, overriding these strategies.  You may also switch either or both players' strategies mid-game, though of course the goals of those strategies may no longer be realized.
The play may be step-by-step; animated; or all at once:
 <|  |> Do one step forwards or backwards. <  ||  > Animate the steps. <<  >> Clear the game, or jump to the end of the game.
The node values are displayed as follows:
 0,1 The value assigned to the leaf, or calculated as the majority value of the children of a node. ? Not assigned a value yet. X The value is irrelevant because an ancestor's value could already be determined without knowing this node.   The solver will not waste time choosing irrelevant leaves.
If Node View is set to Counts, then the order in which the leaves are assigned 0/1 values is indicated in parentheses after the 0 or 1; if the 10th leaf given a 0/1 value is given the value 0, it is shown as "0 (10)".  If this value is propagated up to ancestors, the order the ancestor nodes are assigned in is denoted "0 (10+1)", "0 (10+2)", etc.  Unassigned descendants of those ancestors are marked irrelevant "X", and the order is denoted in the same sequence, "X (10+3)", etc.

This generalizes to finite trees with all nodes having an odd number of children. The demonstration has all leaves at a specified depth, and has a specified downward degree (odd).

Your browser is not java enabled.