Past exam of the mathematics course of the University of Cambridge / 2007 / ia / Paper 5 / 5 / a / ii

For a finite binary tree, gordon p t expresses the existence of a root-to-Lf path on which every branch-node label satisfies p. The empty tree has a length-zero path and returns true. At Br(x,left,right), such a path exists precisely when p x holds and at least one child admits such a path. This is the recursive Boolean equation derived in part (i).

The property is neither “all labels in the tree satisfy p” nor “some label satisfies p”. A bad label in an unchosen subtree does not prevent success, but a bad root label prevents every root-to-leaf path. The traversal performs a left-first search for a qualifying path.