Amoebas Having Boring Family Trees

Trees are computational data structures used for storing and searching data. Data is stored at tree nodes. Each node can also contain a link to zero or more "children" nodes. These links can be used in a search algorithm to traverse the tree. Correspondingly, each node may have up to one "parent" node. Only one node in the tree, the "root" node, does not have a parent node.

Abby's class project was due tomorrow morning, and she was still not sure what she was doing wrong. As she looked at her paper, panic began to set in.

The example family tree that her teacher had given her showed a clear network of nodes. There were levels for grandparents, parents, and siblings. But, Abby's tree did not look anything like that. Sometimes, being the only amoeba in her second grade class made life complicated.

Being an amoeba, Abby's family worked differently from those of her classmates. Instead of having two biological parents, she had exactly one. She was born through mitosis, when her parent had literally split in half to form her and her sister Venn. So, Abby's tree started at a single grandparent and branched out as it went down. Each parent could have exactly zero or two children, and each child had exactly one parent node. It was a perfect binary tree. Unfortunately, it looked nothing like what the teacher would be expecting.

On the plus side, Abby found it remarkably easy to trace her lineage back for centuries. Each amoeba on her family tree could have only one parent. Thus, she could follow her family all the way back to her great, great, great grandfather, "Sir Edward the Adventurous", who had been the first amoeba to colonize this particular petri dish. And starting at her great great grandfather, she could search down through the layers and find out how she was related to any other amoeba in the whole dish. But, none of that helped on this class project.

Abby carefully finished labeling her tree. She had one grandfather who had two children: her father and her aunt. Her father then had two children: her and Venn. And her aunt also had two children. All three generations formed only seven nodes on the tree.

Discouraged, Abby gave a bubbly sigh of despair as only amoebas can. She only hoped that her teacher would understand.

Epilogue: Abby actually received double credit for her assignment after she launched into a impromptu 30 minute monologue on the wonderful computational properties of her family tree. First, she described how she could determine the exact relationship to anyone in her family in O(log N) time regardless of the number of generations included. Then, seizing the moment of inspiration, she noted that her family tree was in fact a heap sorted by age. Each amoeba in the tree could have up to two children and the ages of both children were strictly less than that of their parent. Her descriptions were so inspiring that the entire class gave her a standing ovation.

.