solution that traverses the tree exactly once, replacing each
leaf as soon as you see it?
- Consider a variation in which you must replace each leaf with
- its number of occurrences in the tree. Is there any way to do
- that with a single traversal?
-
You can assume that the tree is binary, leaf-labeled (no
labels on the internal nodes), and that the leafs are, say,
chars.
- Here is [a hint](/hints/assignment_10_hint).
+ Here is [a hint](/hints/assignment_10_hint_1).
+
+ Consider a variation in which you must replace each leaf with
+ its number of occurrences in the tree. Is there any way to do
+ that with a single traversal? (Here is [a hint](/hints/assignment_10_hint_2).)
+
2. Armed with your solution to problem 1, try this: you have as input a leaf-labeled, binary tree whose labels are strings. You also have as input an interpretation function from strings to meanings. Let the meanings of your strings be primitive elements, for instance: