# 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 parent

• Children: b, d, x, are the children of a

• Siblings: b, d, x, are siblings of each other

• Ancestors: u has ancestors l, d, a

• Descendants: x has s, m as its descendants

• Leaves: 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:
height(T) = 1 + max(height(TL), height(TR)), where if height(null) = -1, which might be counter-intuitive but it follows the mathematical definition of tree height

## 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

## 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 is

• C-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) {
func(curr->data);
preOrder(curr->left);
preOrder(curr->right);
}
}

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

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

## 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