  We investigate an AND-OR tree T and a probability distribution d on the truth
assignments to the leaves. Tarsi (1983) showed that if d is an independent and
identical distribution (IID) such that probability of a leaf having value 0 is
neither 0 nor 1 then, under a certain assumptions, there exists an optimal
algorithm that is depth-first. We investigate the case where d is an
independent distribution (ID) and probability depends on each leaf. It is known
that in this general case, if height is greater than or equal to 3, Tarsi-type
result does not hold. It is also known that for a complete binary tree of
height 2, Tarsi-type result certainly holds. In this paper, we ask whether
Tarsi-type result holds for an AND-OR tree of height 2. Here, a child node of
the root is either an OR-gate or a leaf: The number of child nodes of an
internal node is arbitrary, and depends on an internal node. We give an
affirmative answer. Our strategy of the proof is to reduce the problem to the
case of directional algorithms. We perform induction on the number of leaves,
and modify Tarsi's method to suite height 2 trees. We discuss why our proof
does not apply to height 3 trees.
