TwiddleLab / Code / Data Structures You Can See
Trees: Folders Inside Folders
What you will learn
- A tree has one root; every other node has one parent and any number of children. Nodes with no children are leaves.
- Many things are trees: folders, a family, a tournament, a page's menus, a quiz of yes or no questions.
- To traverse a tree, keep a stack: take a node off, put its children on. With a queue instead, you go level by level.
- Totals like folder sizes are added up from the leaves to the root.
How the lesson goes
Your phone says "Storage almost full".
Only files show a size. Which folder in the top row is eating the space? Tap your bet.
Add it all up, the way the phone does.
A folder's size is the sum of what's inside it. Tap folders as soon as everything inside them is known.
A folder can't know its size until every child has one. So sizes flow upward: files first, then the folders that hold them, and the root last.
How does a program visit every folder?
It keeps a stack, your plates from lesson 1. Press Step and tap what comes off next.
That shape is a tree.
A tree starts at one root. Every other node has exactly one parent and can have children. Nodes with no children are leaves.
Visiting every node is a traversal. With a stack it goes deep first; with a queue it goes level by level.
In Python a tree can be a dictionary from each folder to its list of children: {"Phone": ["Photos", "Music"], "Photos": ["Trip"]}.
Build your own folder tree.
Drag each card into a folder. Put some inside the new folders to make it deeper.
Stack or queue?
Two walkers visited this tree. One kept a stack, one a queue. Tag each order, then Check.
A stack hands back the children you just pushed, so the walk keeps going down. A queue hands back the oldest waiting node, so every node of one level comes before the next level.
Find the hog.
Find the single biggest file on this phone. Open as few folders as you can.
A tree of questions.
AI uses trees too: each node asks a question, each leaf is an answer. Send every critter down to its leaf.
Back to your own tree.
Tap its root and watch the sizes add up from the leaves.
Previous lesson: Sets: Is It In There? · Next lesson: Binary Search Trees · Part of the course: Data Structures You Can See
Lessons are interactive and need JavaScript. Turn it on to play them.
