housekeeping

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

example: height and weight balanced BST

terms to know:

BST operation: insertion

Untitled

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)