Say that we have nodes in a tree and it has a branching factor of 3. At the leaves we have a binary value 1 or 0 (which can be viewed as "votes"). Each parent computes the majority of its children and assigns itself that value ("vote").
What I want to show is that in the worst case, a deterministic algorithm will have to query the value of all of the $n = 3^h$ leaves in order to determine the value assigned to the root.
I do have the following solution which I am having a hard time understanding:
But that algorithm doesn't seem to work in some trivial cases (unless I misunderstood the algorithm).
Say that A just started querying the leaves. So it queries the first leaf and since nothing has been assigned, when it goes to its first ancestor such that at most 1 is determined, since none of his siblings (which in this case are the siblings of the parent of the leaf, the uncles) have been determine, then that leaf is arbitrarily assigned true. When it goes to the next leaf, one should assign it false so that one has to inspect the other leaf, but when if you follow what the adversarial algorithm does it doesn't work. It says to go to the parent of the currently queried leaf and in this case, since still, none of the siblings of the parent have been assigned anything, then one would arbitrarily choose true, which is bad, because it determines the parent to be true without looking at the last leaf node of that subsection!
I am wrong or am I misunderstanding what $B$ is suppose to do?
Why isn't it just optimal to always choose 1 0 1 or 0 1 0 or 1 1 0 or however A queries leaves, to make sure that it always sees two leaf, such that it has to see the other leaf no matter what (i.e. if A sees a 1 to make sure the next thing it sees in that sub section of the leafs to see a 0 etc). I don't understand why we need to consider ancestors. Why does that matter?
For completeness I will provide the full text: