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

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:

• root - get root node
• is root(p) - check if this node is root node
• parent(p) - get parent of p
• numChildren(p) - number of children of p
• children(p) - iterator over p's children
• isLeaf(p) - check if node is leaf

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