housekeeping

• Assignment 1 is released! Please start it early and go to help-sessions early.

function pointers

binary search trees

kinda like a linked list except each node has two ‘children’

every node on the left has a value less than the current node

every node on the right has a value greater than the current node

typedef struct BSTRep *BSTree;

struct BSTRep {
	struct BSTNode *root;
}

struct BSTNode {
	int value;
	struct BSTNode *left;
	struct BSTNode *right;
}

example: height and weight balanced BST

terms to know:

• height / weight balanced

• root / leaf node

• parent / child node

• why BSTs?

BST operation: insertion

BST Traversals

four different ways to traverse a tree:

1. pre-order: visit root, then left subtree, then right subtree
2. in-order: visit left subtree, then root, then right subtree (gives the nodes in order of value)