Trees Study Guide

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
    • 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
• 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:

• $ n $ number of nodes
• $ n_E $ number of external nodes
• $ n_I $ number of internal nodes
• $ h $ height of nodes

Then the following properties hold.

General Binary Tree Properties

General trees - height/number nodes

$ \log{(n+1)} - 1 \leq h \leq n-1 $

$ h+1 \leq n \leq 2^{h+1}-1 $

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:

$ 1 \leq n_E \leq 2^h $

Limit on the number of internal nodes:

$ h \leq n_E \leq 2^h - 1 $

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.

$ \log{(n+1)} - 1 \leq h \leq \dfrac{n-1}{2} $

and rearranging, we get:

$ 2h + 1 \leq n \leq 2^{h+1} - 1 $

Proper trees - number of internal/external nodes

The property mentioned above is

$ n_E = n_I + 1 $

$ h+1 \leq n_E \leq 2^h $

$ h \leq n_I \leq 2^h - 1 $

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