= Solution
For a finite <binary tree>, `gordon p t` expresses \b[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.
Back to article page
