# Trees Study Guide

### From charlesreid1

## Contents

# Definitions and Variations

## Definitions

**tree** - collection of nodes that is either empty, or consists of a root node with 0 or more non-empty subtrees connected to the root by a directed edge

**node** - element of a tree that stores data and has a directed edge connecting it to a parent (unless it is the root node) and one or more children

**parent** - the node above a given node that is referred to directly

**child** - the node below a given node that is referred to directly

**root** - top-level root in tree, only node with no parent

**siblings** - two nodes that share a parent

**internal** - a node with one or more children

**external/leaf** - a node with no children

**descendant** - a node is a descendant of another node if it is a child of that node or a child of its children

**ancestor** - a node is an ancestor of another node if it is a parent of that node or its parent

**abstract class** - clas that is intended to be implemented and lacks implementation details

**concrete class** - actually implements details of the class

**depth of node p** - number of ancestors of p, excluding p (depth of root is 0)

Recursive definition of depth: if p is root, 0; otherwise, 1 + depth of parent

**height of node** - number (max) of nodes to get to a leaf

Recursive definition of height: if p is a leaf, height is 0; otherwise, max( 1 + depth(child)) for child in children

**binary tree** - ordered tree with left or right children

**proper binary tree** - each node has 0 or 2 children

**full binary tree** - same thing as proper

**complete binary tree** - (think heaps) each hierarchical level of the tree is populated completely before moving on to the next hierarchical level

**level numbering** - utilized for array-based binary tree storage

**traversal** - way of accessing each node

**preorder traversal** - traversal in which ROOT node is visited FIRST

**postorder traversal** - traversal in which CHILDREN nodes are visited FIRST

**breadth-first traversal** - traversal that visits all nodes of depth d before visiting any nodes of depth d+1

**in-order traversal** - traversal in which LEFT children are visited, then NODE is visited, then RIGHT children are visited

**binary search tree** - binary tree in which left node value > this node value > right node value

**Euler tour** - walks around the entire tree, moving left, visiting each node twice (pre-traversal and post-traversal)

**template method pattern** - describes a generic computation method that can be specialized for certain steps or parts

# ADTs and Interfaces

Tree navigation and node methods:

- getRoot(p) - gets root node of tree containing p
- getParent(p) - returns node that is parent of p
- getChildren(p) - iterator over children of p
- isRoot(p) - boolean, is p the root node
- isLeaf(p) - boolean, is p a leaf node
- numChildren(p) - int, number of children of p

Tree construction methods:

- add root
- add left/right/child
- replace
- delete
- attach

Tree utility/general methods:

- size
- empty
- clone
- clear
- equals

Binary tree methods:

- left
- right
- sibling

# Implementations

Tree Position/Node class:

- parent
- left/right/container for children
- protected attributes - accessible to parent or exposed via get/set
- get/set for element
- get/set for parent
- get/set for children

Tree class:

- root
- size
- make position (protected)
- validate (protected)

Strategy:

- public methods call private recursive methods
- insert/remove/contains have public/private versions
- traversal methods all private

# Algorithms for Operations

Algorithms for tree operations:

height(p) method:

- if p is root:
- return 0

- else:
- return 1+height(parent)

depth(p) method:

- if p is leaf:
- return 0

- else:
- return 1+max( depth(child1), depth(child2), ... )

clone method (public):

- new tree
- root = clone this root
- return tree

clone method (private recursive):

- if node null:
- return null

- else:
- create new Node
- set left to clone node left
- set right to clone node element right
- return new node

addRoot method:

- deal with non empty case
- root = new node
- update

addLeft or addRight method:

- deal with non-empty case
- left = new node or right = new node

replace method:

- node element =new element

attach(p,tree1,tree2) method:

- deal with internal node case
- set parent of tree 1 root node to p
- set left child of p to tree 1 root
- set parent of tree 2 root node to p
- set right child of p to tree 2 root
- tree1 root = null, size = 0
- tree2 root = null, size = 0

delete method:

- deal with 2 child case
- get correct child
- deal with root case
- get cursed node's parent
- update parent's left/right child to point to replacement
- convention: node parent = node

preorder subtree traversal:

- perform visit action for p
- for each child of p:
- preorder(c)

postorder subtree traversal:

- for each child of p:
- postorder(p)

- perform visit action for p

inorder subtree traversal:

- if p has left:
- inorder(left)

- perform visit action for p
- if p has right:
- inorder (right)

breadth-first traversal:

- deal with empty case
- create queue
- while queue not empty:
- pop node from queue
- perform visit action on node
- add children to queue

postfix expression tree builder:

- create tree node stack (last pop will be root)
- while next char in expression:
- take next char
- if numeric:
- make new node
- add to stack

- if operator:
- new node
- left = pop
- right = pop
- add node to stack

infix expression tree builder:

- create tree node stack
- set start new expression is true
- while next char in expression:
- take next char
- 4 cases: numeric, operator, (, or )
- if numeric:
- make new node
- if start of new expression:
- push node onto stack
- start new expression is false

- else if expression on stack:
- if peek stack is operator and peek stack has 1 child,
- add to right child of peek

- else error

- if peek stack is operator and peek stack has 1 child,
- else error

- if operator:
- new node
- set left to stack pop
- stack push node

- if (:
- start new expression is true

- if ):
- if stack size > 1:
- pop top
- add to keep's right

- if stack size > 1:

- when finished,
- while stack size > 1:
- pop top
- seek peek right to top

# Properties of Binary Trees

For a non-empty tree T with n nodes and the following characteristics:

- number of nodes
- number of external nodes
- number of internal nodes
- height of nodes

Then the following properties hold.

## General Binary Tree Properties

### General trees - height/number nodes

This is a natural maximum/minimum limit on the number of nodes that any given level can hold. The lower limit corresponds to the case of a binary tree that looks like a linked list, the upper limit corresponds to a full binary tree.

### General trees - number of internal/external nodes

Limit on the number of external nodes:

Limit on the number of internal nodes:

## Proper Binary Tree Properties

Recall from definitions above that proper binary tree is one in which each node has 0 or 2 children.

### Proper trees - height/number nodes

The following properties relate the height of a complete/proper binary tree to the number of nodes.

and rearranging, we get:

### Proper trees - number of internal/external nodes

The property mentioned above is

# Complexity and Cost

Big-O Complexity of Lists | |||
---|---|---|---|

Linked Binary Tree | |||

depth | O(d) | ||

height | O(h) (O(n) worst case) | ||

children | O(c) | ||

tree traversal, euler tour | O(n) | ||

add/replace/attach | O(1) (given a position) | ||

root/parent/child/sibling | O(1) (given a position) | ||

is root/is leaf | O(1) | ||

length | O(1) | ||

empty | O(1) |

# OOP Principles

Delegating responsibility for tasks:

- Many decisions to make about inheritance, protection, ownership of operations
- Example: should the method for getting the left/right node be node.left? node.getLeft()? tree.left(node)?
- When designing a data structure, have to
**think ahead**to concrete implementations. What will you need to override, and what will stay the same? - Trees have a complicated potential inheritance diagram.
- Different concrete implementations (linked vs array)
- Different functionality (AVL vs BTree vs Red Back)
- Further, internal classes and utilities might need to change (e.g., AVL trees keeping count)
- Trees are used by other data structures (priority queue, set, sort, etc)

- Nail down the scope before you start, to keep from (a) putting in way more work and formality than is required, or (b) putting together a slapdash design that has to be completely refactored
- Seems better to build functionality into the tree - more self-contained - although if you can get away with node.left, why wouldn't you

Adaptability and reusability:

- Hook methods - pseudo-virtual methods
- Template method pattern
- Generic types for node data
- Generic types extend from nodes to trees

# Flags

TreesSeries on Data Structures Abstract data type: Trees/ADT Concrete implementations: Trees/LinkedTree
Preorder traversal: Trees/Preorder Postorder traversal: Trees/Postorder In-Order traversal: Binary Trees/Inorder Breadth-First Search: BFS Breadth-First Traversal: BFT Depth-First Search: DFS Depth-First Traversal: DFT OOP Principles for Traversal: Tree Traversal/OOP Tree operations: Trees/Operations Performance
Finding Minimum in Log N Time: Tree/LogN Min Search
Abstract data type: Binary Trees/ADT Concrete implementations: Binary Trees/LinkedBinTree Binary Trees/Cheat Sheet
· Template:TreesFlagBase · e |