trees 🌲

trees as a form of data structure

e.g. file system

trees are connected graphs that has:

key terms describing trees

root = node with no parents (the ‘start’ of the tree)

internal node = node with both parent(s) and children

leaf = node with no children

parent node =

child node =

binary search trees (BSTs) ✌️

tree where $k=2$ (each node has two children)

why we need binary trees

binary search is a necessary algorithm to use for large sets of numbers (much quicker than linear search) — but it requires a sorted structure

arrays have

linked lists have


a binary tree tries to take the ‘best of both worlds’

instead of using complex algorithms to do these operations, we will instead store the data in a complex data structure to simplify our algorithms

(note: the trade-off between time and memory usage)

definition + properties

BSTs have a recursively defined structure: a BST either is

BSTs are ordered trees

some key terms:

operations

some possible operations include