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

Graph Algorithms