Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming / 5 / e

Define the directed successor relation by $E(u,v)⟺l(u)=c(v)\vee r(u)=c(v)$. Then the required predicate iswhere $v(u)$ denotes the natural-number information component of node $u$. In the source's indexed notation this is $\forall n_i,n_j\in T,(l_i=c_j\vee r_i=c_j)\Rightarrow v_i<v_j$.

This formulation checks both successor links against every node with the corresponding identifier, so it does not silently assume part (d)'s uniqueness condition. It checks existing successors; if every identifier must denote an actual node, add the separate referential integrity condition $\forall u\in T,\exists v,w\in T,c(v)=l(u)\wedge c(w)=r(u)$, or exempt an explicitly designated null identifier. The source specifies no null convention. Indeed a nonempty finite structure with two actual successors at every node cannot have strictly increasing values along all edges: following successors would eventually create a directed cycle. The implication above remains meaningful for leaves represented by absent or null successors.