In this lecture, we'll introduce trees as a new linked data struture and learn about different ways of traversing them.
- 📚 Readings: Text 16.1
- 📝 Lecture quiz on Canvas
- 🎬 Lecture video on Canvas [toggle visibility]
- 📎 tree-notes.pdf
Contents
1. Topic Overview
2. Binary Trees and the TreeNode Struct
3. What's next?
4. Exam Prep
Topic Overview
Attachment: tree-notes.pdf
We talked about trees today in what was mostly a conceptual lecture. We discussed a LOT of tree-related terminology, some of which was a review of material we saw in our lecture on binary heaps. We also saw binary search trees (BSTs) for the first time and discussed best-, worst-, and average-case runtimes for insertion and search in BSTs. (A discussion of the deletion algorithm is postponed until next time.)
We also explored the first few tidbits of what it looks like to have a node-based implementation of binary trees that relies on a TreeNode struct. (For more on that, see the section below.)
We solved a few puzzles along the way, as well, and we concluded our lecture with three tree traversal algorithms: pre-order, post-order, and in-order.
See today's lecture video and the PDF attached above for all the juicy details!
Today's lecture notes are a bit sparse because because the hand-written notes presented in class and attached above serve -- to some degree -- as lecture slides. I encourage you to create your own lecture notes that summarize the key topics from today's lecture, as well!
Binary Trees and the TreeNode Struct
Trees are another node-based data structure, like linked lists. When we first encountered trees in the form of binary minheaps, we used an array as our underlying representation. That representation worked, in part, because our binary minheaps are complete binary trees, and so the array representation fills up from left to right with no gaps (no wasted space).
In contrast, today's lecture served as an introduction to an actual node-based representation of binary trees. Suppose, for example, we have the following representation of a binary tree:
We saw today that we can represent such a tree with a TreeNode struct that contains two child pointers -- left and right -- like so:
struct TreeNode
{
int value;
TreeNode *left;
TreeNode *right;
};
In memory, the actual node-based representation underlying such a tree becomes something like the following (where the memory addresses are, of course, works of fiction). Note the use of a root pointer that stores the address of the tree's root node and which serves as our sole entry point into the tree, much in the same way that a head pointer serves as an entry point to a linked list:
What's next?
Tomorrow (Thursday), we'll continue our discussion of BSTs. We'll cover the algorithm for deleting elements from a BST, solve a few more binary tree related puzzles, discuss BST applications, and start coding them up from scratch.
Exam Prep
1. Code up two BST insertion functions: one iterative and one recursive. The function signature and Node struct are as follows:
struct Node
{
int data;
Node *left;
Node *right;
Node(int val)
{
data = val;
left = right = nullptr;
}
};
bstInsert(Node*& root, int data)
{
// CODE ME
}
2. Why is it necessary to pass the Node pointer by reference in the bstInsert() function signature above?
3. Give the pre-, post-, and in-order traversals for the following binary tree:
23
/ \
11 57
\ \
19 89
/ \
81 99
Highlight for solutions to Exercise #3:
- Pre-order: 23, 11, 19, 57, 89, 81, 99
- Post-order: 19, 11, 81, 99, 89, 57, 23
- In-order: 11, 19, 23, 57, 81, 89, 99
4. Write functions to print the pre-, post-, and in-order traversals for a binary tree. Test them out by constructing a binary tree (possibly using your bstInsert() function from above), manually tracing through the tree to see what those traversals should be, and then running your program to check that its output for each traversal matches your expectations.
5. How could you write a test case (using our SimpleTest framework) that verifies whether your tree traversal functions are visiting nodes in the correct order?
6. As always, the textbook and this week's section handout are chock full of great exercises and additional examples and explanations to help reinforce this material.