Construction of a Binary Tree

In this applet, you will find two distinct binary trees drawn below. Each such tree is drawn with the convention that internal nodes are displayed as red circles, and external nodes are displayed as black squares.

The first binary tree below is randomly generated by the Applet for a given size. The second binary tree is initialized as a single external node.

Your goal is to build up this second tree node-by-node so that it appears identical to the first given tree. In particular, each time you click on an external node of the second tree, that node will be expanded into an internal node with two new external children (the so called expandExternal method of the text).

If you think you have successfully completed the task, you may click on the "Validate Correctness" button to check your work. If you feel you need to restart, you may begin again, though it will be on a newly generated tree.



Michael Goldwasser