Kotlin
Java

Trees
Kotlin

Created By: Geoffrey Challen
/ Updated: 2021-10-30

This lesson introduces a new data structure: trees. Trees are extremely useful, both for modeling certain types of data, and for enabling certain algorithms. They are also great for practice with recursion! Let's do this...

What is a Tree?

Wikipedia defines a (computer science) tree as:

In computer science, a tree is a widely used abstract data type that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.

Let's look at some diagrams that will help visualize this new data structure, and introduce some important terminology.

Show a diagram of a tree and review various terminology: root, parent, child, etc.

What are Trees For?

Trees can be used to model a variety of hierarchical data. Examples include:

  • The Kotlin Class Hierarchy, since each class has one parent but possibly multiple children
  • Internet domain names, with .edu being one of the root's children (.com) is another, .illinois being one of the children of .edu (.purdue) being another, and so on
  • The files on your computer

Let's look at these example a bit more:

Go through various examples of trees in real life, including (but not limited to) the examples listed above.

We'll also see ways that trees can be used to store a collection of items in ways that enable certain efficient algorithms. For example, by storing data in a tree, we can enable more efficient search algorithms than the O(n) scans of arrays we've seen so far. We'll get there!

Binary Trees

Most of the work with trees that we'll be doing is on a specific type of tree called a binary tree. Binary trees are so named because each node has up to two children, but no more.

Let's develop the BinaryTree class that we'll use in class and that we'll use on upcoming homework problems. Note that this is available in the playground environments and homework as cs125.trees.BinaryTree. As a way of reviewing object design and references, let's walk through the process of designing this class:

Recursion on Trees

Yesterday we introduced recursion, a problem solving technique that works by breaking down large problems into smaller pieces, solving them, and then combining the results. Binary trees are a great fit for recursion! Let's see why:

Point out that each subtree of a tree is, itself, a tree, and hint at how we can use this in our recursive algorithms.

In addition, compared to lists and arrays and Strings, trees are hard to work with using iterative solutions! Recursion is a much better approach...

Recursive Tree Sum

Let's get some practice with recursion on trees. We'll take a tree filled with integer values and determine the sum of all the values it stores. Along the way, we'll look at several recursive approaches, and begin to develop some of the patterns that we'll use working recursively with binary trees.

Go through how to compute the sum of a binary tree. Show both the null-avoiding and null-safe approaches.

Recursive Tree Size

To help you prepare for our next homework problem, let's discuss the recursive approach to counting the number of nodes in a tree.

Use a diagram to show how to count the nodes in a binary tree.

Computational Complexity

Let's pause for a moment to discuss how we evaluate the complexity of your homework submissions, and what you can do to improve your code when we indicate that it is too complicated. First, a practice problem to work on. Once you've solved this, the solution walkthrough will show what happens to an overly-complex submission, and discuss how to reduce the complexity of your code.

The practice problem below looks like a regular practice problem, but it introduces a new way in which we'll begin scoring your homework solutions: evaluating their complexity. Starting today there is 1 point out of 10 you'll earn for not submitting an overly-complex solution. Solve the problem and then watch a solution walkthrough to learn more!

Show how to complete the homework problem above. Feel free to cover multiple approaches!

Solution Walkthrough

Show how to complete the homework problem above. Feel free to cover multiple approaches!

Solution Walkthrough

Show how to complete the homework problem above. Feel free to cover multiple approaches!

Solution Walkthrough