Binary Search Tree with Owls

I like many different kinds of trees — but my favorite tree is a binary search tree. When I taught an undergraduate course on data structures at UT Austin, my favorite final exam question involved removing an item in a binary search tree or rebalancing a heap. I hope my PhD students’ favorite trees are “abstract syntax trees” since most of my PhD students work on software analysis and tooling, and their research involves traversing, manipulating, and extracting information from abstract syntax trees.

So I started asking questions to Sophia and her friends — what is your favorite tree? Their answers are flower trees, fruit trees, rainbow trees, and rainbow flower fruit trees. I told Sophia and her friends that in computer science, most trees are upside down. To make a point, I put a tree poster upside down with key terms such as a trunk, branch, and leaf.

Then I brought owl cards which I made by putting number stickers on them. A binary search tree is a data structure designed for fast look-up and containment checking. Each node has two children, where the left child is less than its parent and the right child is greater than its parent.

Explaining to kids that in computer science we like drawing trees up side down.

Then we started inserting owls to a binary search tree. I will first ask each kid to select an owl card. (Sophia loves pink!) Then we will start from the root of the tree to see which node we can insert the owl card in.

Sophia is finding a node to insert an owl card in. Each owl card has a number and we need to observe L/R constraint of BST.

Sophia and her friend Iris created their own binary search tree by gluing each owl card one at a time on the poster.

Placing owls in the binary search tree.

Then I talked about how many owls are in the tree in total. Then I counted the depth of the tree. The point of a binary search tree data structure is that, on average, it provides log n time for look up when the tree has n nodes. So I explained to Sophia about how many more owls are there, compared to the depth of the tree. We also used the binary search tree, to check whether the certain number owl is contained by simulating a particular look up traversal path — for example, do we have a owl with the number 5 on this tree?