#Implementing trees#
-In [[Assignment3]] we proposed a very ad-hoc-ish implementation of trees.
+In [[Assignment3]] we proposed a very ad-hoc-ish implementation of
+trees. It had the virtue of constructing trees entirely out of lists,
+which meant that there was no need to define any special
+tree-construction functions.
Think about how you'd implement them in a more principled way. You could
use any of the version 1 -- version 5 implementation of lists as a model.
/ \
1 2
-Linguists often use trees of this sort. The inner, non-leaf nodes of the
+The inner, non-leaf nodes of the
tree do have associated values. But what values they are can be determined from
the structure of the tree and the values of the node's left and right children.
So the inner node doesn't need its own independent label.
However, when using trees as a computational tool, one usually does have
latitude about how to structure a larger tree---in the same way that we had the
-freedom to implement our sets with lists whose members were just appended in
-the order we built the set up, or instead with lists whose members were ordered
-numerically.
+freedom to implement our [sets](/week4/#index9h1) with lists whose members were
+just appended in the order we built the set up, or instead with lists whose
+members were ordered numerically.
When building a new tree, one strategy for where to put the new element and
where to put the existing tree would be to always lean towards a certain side.