Outline

• recursive linked list methods
• problem solving with recursion
• trees
• binary search trees
• tree traversal
• binary search tree algorithms: add, remove, traverse
• binary node class

recursive data structures

• a linked list is essentially a recursive data structure: each node within a linked list is the head of a (perhaps smaller) linked list
• it is easy to write recursive linked list methods
• for example, to add, just return the new linked list with the new value inserted
• to remove, each recursive call can return the new linked list with the given value removed
• the implementation of LinkedListRec.java differs from the implementation in the book (and in my opinion, is simpler and clearer)
• returning a new linked list, even it if is identical to what was passed as a parameter, is a very powerful operation

problem solving with recursion

• many classical puzzles have recursive solutions
• for example, there is a game, Towers of Hanoi, which has three pegs and a number of discs of varying size
• each disk can go on any peg
• the game starts with all the disks on one peg
• disks are moved one at a time
• any disk D can be moved to any peg on which the topmost disk is larger than D
• the objective of the game is to move all the disks from one peg to another
• see here for an example of the actual game
• it has been said that there are monks in a monastery in Hanoi patiently engaged in moving 64 disks from one peg to another -- when they are done, the world might come to an end
• if this were true, how long would it take for the world to come to an end?

Solution to the Towers of Hanoi

• it is easy to move the smallest disk from one peg to another
• it is easy to move any disk D to another peg where the topmost disk is larger than D
• how do we move a set of n disks from peg 1 to peg 2?
• assume (recursively) that I know how to move a set of n-1 disks from peg 1 to peg 3
• and also from peg 3 to peg 2
• then, I do the first step (move the n-1 disks), then move the nth disk from peg 1 to peg 2, and finally move the n-1 disks back from peg 3 to peg 2
• of course, to move the n-1 disks from peg 1 to peg 3, I have to move the top n-2 disks from peg 1 to peg 2, then move the n-1th disk from peg 1 to peg 3, and finally move the n-2 disks from peg 2 to peg 3
• I can continue this until my base case, n == 1, where I can move the disk directly
• This is very easy to do recursively, and much harder to do iteratively
• See Towers.java

Finding a path through a maze

• finding a path through a maze is easy:
  • at the exit, conclude that the path has been found
  • at a dead end, conclude that the path has not been found
  • whenever there is a choice, recursively explore all choices
  • after marking the current location so we will not explore it again
• a tricky part of this is to find ways to mark a location so we can tell, when we visit it, whether it is:
  • known to be part of the path, or
  • known to have been visited already, or
  • not visited yet
• this requires a few bits at each position in the maze
• the program in the book represents these using colors

Backtracking

• finding a path through a maze is an example of a technique called backtracking
• if we have several choices, and we are not sure which one will work, we try one of them, and look at the result
• if the result is not favorable, we try the next choice
• this is done recursively, because we have more choices once we have made the first choice
• this can be useful in some games, such as chess or go
• however, exhaustively searching all possible moves is impractical
• instead, the search goes up to a point, estimates how good the play is at that point, and reports that
• in a two-player game, have to consider my best move in response to my opponent's best move -- my opponent's best move is the one that gives the lowest score, my best move is the one that gives the highest score

garbage collection

• garbage collection is easy:
  • start with the system stack and all the global variables
  • follow each of the pointers, marking each location as visited
  • at the end, any location that has not been visited, is free and can be reused
• we need to mark each of the memory areas as being in use or not
• one bit (or two colors) is sufficient

trees

• imagine having to store, in an organized fashion, all the descendants of a given person
• as in this family tree:
  image by Derrick Coetzee, in entry " family tree" in Wikipedia
• trees can hold any kind of data, even numbers:
  image by Derrick Coetzee, in entry " Tree (data structure)" in Wikipedia
• a node in a tree is similar to a node in a linked list, except:
  • a linked list node has a reference to zero or one other link nodes, whereas
  • a tree node has a reference to zero or more other tree nodes
• later we will consider how trees are implemented

Tree properties

• a tree has one root node, from which all other nodes can be reached by following links
• each node in a tree, except the root node, has exactly one parent
• each node in a tree can have zero or more children
• the other children of a node's parent are the node's siblings
• nodes are in a hierarchical relationship:
  • node X is an ancestor of another node Y, or
  • node X is a descendant of another node Y, or
  • node X is on a different branch than node Y
• nodes without children are leaf nodes
• nodes with children and a parent are interior nodes

Tree properties exercise

image by Derrick Coetzee, in entry " Tree (data structure)" in Wikipedia
• in-class exercise: identify the
  • root node
  • interior nodes
  • leaf nodes
  • parent of node 6
  • children of node 6
  • ancestors of node 5
  • descendants of node 7

more tree definitions

• a subtree is a node with all its descendants
• the level of a node is the number of its ancestors, so e.g. the root is always at level 1:
  • the children of the root are at level 2
  • their children are at level 3
  • the children of a node at level n are at level n+1
  sometimes the word depth is used instead of level
• the height of a tree is the maximum depth of any node in the tree
• in a binary tree each node has at most two children
  --- likewise, in a ternary tree each node has at most three children

types of binary trees

• in a balanced binary tree the depth of each subtree of every node differs by at most one (this is a recursive definition)
  --- there are also other definitions of balanced binary trees
• in an expression tree, each internal node contains an operator, and each leaf node is an operand (value)
  --- subtrees are evaluated first, yielding a value. Once all its children have been evaluated, we can evaluate a node
• in a Huffman tree, each internal node has two children. Each leaf node represents something to encode, such as a letter. The binary string to encode the letter is found by going down the tree from the root to the leaf. Each time we go left contributes a 0 bit to the code, and each time we go right contributes a 1 bit to the code.
• in a binary search tree each node has a value greater than every node in its left subtree, and less than every node in its right subtree
• in a full binary tree, each node has either 0 or two children
• a perfect binary tree of height n has 2ⁿ - 1 nodes, of which 2^{n - 1} are leaves
• a complete binary tree is a perfect binary tree up to the last level. All the leaves at the lowest level are as far to the left as possible.