# Trees

• Tree: a relation in which there is a uniqiue path from the root to the other vertexes
• Root $v_0$: the root node
• Rooted tree: $(T, v_0)$:
• Geometic properties
• $v_0$ is the only root of $T$
• Tree's have cycles
• $v_0$ has in-degree 0, $v != v_0$ has in-degree 1
• Relational properties
• Irreflexive
• Assymmetric
• Not transitive (inverse of transitive)
• Terminology
• Level: steps from root node, starts at zero
• Height: number of largest level
• Siblings: nodes with the same parent
• Leaves: nodes that have no children
• Ancestors: all connections upwards
• Descendants: all connetions downards
• n-tree/n-ary tree: each vertex has at most n children
• Complete n-tree: each vertex has exactly n children (except for the leaves)
• Binary tree: name for 2-trees
• Positional tree: positive integers as child positions $1, ..., n$ (ordered)
• Labeled trees: each node has a label attached to it
• Subtree
• $B_v$ set of all decendatns of $v$
• Subtree: $T(v) = T \cap (B_v \times B_v$ restriction of $T$ to $B_v$
• Is also a tree

## Examples/applications of trees #

• Syntax tree: used in compilers and calculators
• Draw by reading from outside to the inside
• Huffman code: follow edges in order of bits until you get to a label, repeat from the root node until all bits are decoded
• Binary search tree
• Tries/prefix trees
• Character encoding

Linked-list representation: method to create a binary tree from a general tree to apply search on it

• Left edges: relations from parent to first child.
• Right edges: the siblings (in order of the tree).

### Depth-first search (DFS) #

On a binary tree, in which: Node (N), Left (L), Right (R):

• Preorder search (NLR)
• Inorder search (LNR)
• Postorder search (LRN)

## Undirected trees #

• Undirected tree: the symmetric closure of a tree
• Undirected edge: $\{a, b\}$ = $(a, b), (b, a)$
• Graphs instead of digraphs (lines represent undirected edges)
• Adjacent: a and b are adjacent if there is an undirected edge between them

## Spanning Trees #

Let $R$ be a symmetric connected relation:

• Spanning tree: exactly the vertices of $R$, can be obtained by deleting edges from $R$
• Weighted graphs: graph in which every edge has a weight
• Undirected spanning tree: the symmetric closure of a spanning tree
• Minimal spanning tree: an undirected spanning tree for which the weight is minimal
• Algorithms:
• Prim's algorithm: adds one vertex at a time and checks for minimality
• Kruskal's algorithm: sort edges by weight and add one edge at a time and check for acyclicity