= Solution
An <Oberon> <pointer> refers to a record containing an <integer> label and two <subtree> references:
``
TYPE
Tree = POINTER TO Node;
Node = RECORD
left, right: Tree;
label: INTEGER
END;
``
Use `NIL` for the empty <binary tree>, including either absent child. The <representation invariant> requires a finite, acyclic <binary tree> with disjoint left and right <subtrees>. In particular, shared nodes would represent a different structure and invalidate destructive traversal arguments.
$$
\boxed{\texttt{Leaf}\longleftrightarrow\texttt{NIL},\qquad\texttt{Fork}\longleftrightarrow\text{one allocated record}.}
$$
Back to article page
