Binary Trees, Binary Search Trees, and Tree Traversals

Friday, May 15

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

Contents

1. Topic Overview

2. Binary Trees and the TreeNode Struct

3. What's next?

4. Exam Prep

Topic Overview

Attachment: tree-notes.pdf
This PDF includes a preview of four traversal algorithms we will cover on Monday.

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.

See 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:

Consider the following line of code (which, given the above tree, should print 9 to the screen):

cout << root->left->right->value << endl;

Here's a step-by-step explanation of how that line of code is working:

root contains the memory address of our root node
root-> dereferences that address; it goes to that node in memory
root->left accesses the left field in that root node that we just arrived at
root->left-> now dereferences that address; it goes to the root's left child (i.e., it goes to the 3 node)
root->left->right accesses the right field in the 3 node that we just arrived at
root->left->right-> dereferences that address; it goes to 3's right child (i.e., it goes to the 9 node)
root->left->right->value accesses the value field in the 9 node that we just arrived at

What's next?

On Monday, 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. 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.