Read Section 9.4 in EOPL.
The sameFringe problem is a classic illustration of coroutine behavior. The fringe of a binary tree is the list of leaves encountered in a preorder traversal of a tree. We assume that the values at the leaves are integers greater than 0. For example, the fringes of both the following trees:
are:
1 2 3 4 5 6The easy way to determine if two binary trees have the same fringe is to compute the fringe of each tree producing two lists of numbers and then test these two lists for equality. This solution is far from being efficient as it must traverse both trees, store the fringes in intermediate lists, and then compare them. This may be a complete waste of time if the two trees differ in the value of the first node in their fringe lists. (For example, if the second tree had a 7 in the leftmost node.) A much better solution is to set up two coroutines for traversing each tree in preorder. When a leaf is encountered during the traversal of the first tree, we store the continuation in a local variable, and resume the traversal of the second tree. When a leaf is encountered during this latter traversal, we also store the continuation in a local variable, and compare the values of the two leaves. If they are equal we resume the traversals. Otherwise, we have determined that the two trees do not have the same fringe and we can immediately terminate the program. This solution can be expressed in Scheme as follows:
(define sameFringe
(lambda (tree1 tree2)
(let ((gen1 (make-generator tree1))
(gen2 (make-generator tree2)))
(driver gen1 gen2))))
(define driver
(lambda (gen1 gen2)
(let ((leaf1 (gen1))
(leaf2 (gen2)))
(if (= leaf1 leaf2)
(if (zero? leaf1)
#t
(driver gen1 gen2))
#f))))
(define make-generator
(lambda (tree)
(letrec ((caller '*)
(generate-leaves
(lambda ()
(letrec ((loop (lambda (tree)
(if (leaf? tree)
(call/cc (lambda (genrest)
(set! generate-leaves
(lambda () (genrest '*)))
(caller tree)))
(begin (loop (car tree))
(loop (cadr tree)))))))
(loop tree)))))
(lambda ()
(call/cc (lambda (k)
(set! caller k)
(generate-leaves)
(caller 0)))))))
;; abstract data type for tree
(define leaf? number?)
(define subtree? pair?)
(define tree1 '(((((((((((((1 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14))
(define tree2 '(1 (2 (3 (4 (5 (6 (7 (8 (9 (10 (11 (12 (13 14))))))))))))))
(define tree3 '(2 (1 (3 (4 (5 (6 (7 (8 (9 (10 (11 (12 (13 14))))))))))))))
or if you prefer continuation-passing style:
(define sameFringeCPS
(lambda (tree1 tree2 k)
(make-generatorCPS tree1 (lambda (gen1)
(make-generatorCPS tree2 (lambda (gen2)
(driverCPS gen1 gen2 k)))))))
(define driverCPS
(lambda (gen1 gen2 k)
(gen1 (lambda (leaf1)
(gen2 (lambda (leaf2)
(if (= leaf1 leaf2)
(if (zero? leaf1)
(k #t)
(driverCPS gen1 gen2 k))
(k #f))))))))
(define make-generatorCPS
(lambda (tree k)
(letrec ((caller '*)
(generate-leaves
(lambda (k)
(letrec ((loop (lambda (tree genrest)
(if (leaf? tree)
(begin
(set! generate-leaves
(lambda (k) (genrest '*)))
(caller tree))
(loop (car tree) (lambda (d)
(loop (cadr tree) genrest)))))))
(loop tree k)))))
(k (lambda (k)
(set! caller k)
(generate-leaves (lambda (d) (caller 0))))))))
;; abstract data type for tree
(define leaf? number?)
(define subtree? pair?)
(define tree1 '(((((((((((((1 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14))
(define tree2 '(1 (2 (3 (4 (5 (6 (7 (8 (9 (10 (11 (12 (13 14))))))))))))))
(define tree3 '(2 (1 (3 (4 (5 (6 (7 (8 (9 (10 (11 (12 (13 14))))))))))))))
Your job is to write the solution in Java.