• dynamic non-linear data structure
• access point through the root
  • the root is the pointer to the top-most node of the tree
• each node may have non to many children
• recursive —> each tree is made of subtrees
• search —> $\mathcal{O}(\text{log}(n))$ under reasonable assumptions
  • otherwise $\mathcal{O}(n)$
• we deal primarily with binary trees, where every node has at most two children: left and right

Height

Size

Tree Types

Levels

Traversal