# 4 Trees

Trees are a hierarchical data structure with a certain set of properties that distinguish it from graphs. Trees are rooted, which means that there is a pointer to the root node and each child node can be reached via the root.

## 4.1 Basic tree terminology

(adapted from CS 173) * Vertex: “nodes”

Path: sequence of edges

Parents: Node

**b, d, x**have Node**a**as their parentChildren:

**b, d, x,**are the children of**a**Siblings:

**b, d, x,**are siblings of each otherAncestors:

**u**has ancestors**l, d, a**Descendants:

**x**has**s, m**as its descendantsLeaves: Vertices with no children

## 4.2 Tree Property: Height

**Computation of the tree height**- The length of the longest path from the root to the leaf (count edges).
- If we want to compute recursively:

## 4.3 Tree Property: Binary

- A binary tree is either
- T = {TL, TR, r}, where TL, TR are binary trees
- T = {} = \(\emptyset\)

## 4.4 Tree Property: Full

- A binary tree is full
*if and only if*- Either: F = {}
- Or: F = {TL, TR, r} where TL, TR both have either 0 or 2 children

**Theorem**: A binary tree with n data items has n+1 null pointers.

## 4.5 Tree Property: Perfect

- A perfect tree Ph is defined by its height
- Ph is a tree of height
**h**, with- P-1 = {}
- Ph = {r, Ph-1, Ph-1} when h>=0

- Ph is a tree of height

## 4.6 Tree Property: Complete

(as defined in data structures) * A complete tree is * A perfect tree except for the last level

All leaves must be pushed to the

**left**Or, recursively, a complete tree

**Ch**of height**h**isC-1 = {}

Ch = {r, TL, TR} where

- Either: TL = Ch-1 and TR = Ph-2 Or:TL = Ph-1 and TR = Ch-1

- Full does not imply perfect, so as complete does not imply perfect
- Not full implies not perfect, thus perfect implies full; perfect also implies complete too.

## 4.7 Tree Traversals

(practice them here: https://yongdanielliang.github.io/animation/web/BST.html) * Pre-Order: process the data first, then left child, then the right child * In-Order: left child, process the data, right child * Post-Order: left child, right child, process the data last

```
void BinaryTree<T>::preOrder(TreeNode * cur) {
if (cur != NULL) {
(curr->data);
func(curr->left);
preOrder(curr->right);
preOrder}
}
void BinaryTree<T>::inOrder(TreeNode * cur) {
if (cur != NULL) {
(curr->left);
preOrder(curr->data);
func(curr->right);
preOrder}
}
void BinaryTree<T>::inOrder(TreeNode * cur) {
if (cur != NULL) {
(curr->left);
preOrder(curr->right);
preOrder(curr->data);
func}
}
```

## 4.8 Searching Trees

BFS: breadth first search: visits nodes at each level (level-order traversal): use a queue

DFS: depth first search: find the endpoint of the path quickly (in order, pre order or post order): use a stack

Traversal vs Search: traverse visits every node vs search visits nodes until you find what you want