The Ruby Way: Solutions and Techniques in Ruby Programming, Second Edition

9.3. Working with Trees

I think that I shall never see

A poem as lovely as a tree...

—“Trees,” [Alfred] Joyce Kilmer

Trees in computer science are a relatively intuitive concept (except that they are usually drawn with the “root” at the top and the “leaves” at the bottom). This is because we are familiar with so many kinds of hierarchical data in everyday life, from the family tree to the corporate organization chart to the directory structures on our hard drives.

The terminology of trees is rich but easy to understand. Any item in a tree is a node; the first or topmost node is the root. A node may have descendants that are below it, and the immediate descendants are called children. Conversely, a node may also have a parent (only one) and ...