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?
four different ways to traverse a tree: