Recursion on Trees

Trees are naturally defined recursively. For example, we can define a binary tree as either

(1) empty or
(2) a value together with a left binary tree and a right binary tree.

A more general tree can be defined as:

A tree is a value (the root value) together with a set of trees, called its children.

Such recursive definitions lend themselves naturally to recursive methods that process trees in some fashion. Here, we provide models for two kinds of functions that process trees:

(1) functions that count how many nodes of a tree have a certain property, and

(2) functions that search for a node with a certain property.

Master these two models and you should have an easy time writing recursive methods that process trees.

1. A model for counting nodes of a tree

Eleanor Birrel develops a recursive function for counting the number of leaves of a general tree, where a leaf is a tree whose set of children is empty. (2:6 minutes) Read it here: countNodes.pdf.

2. A model for searching for a node with a certain property

Eleanor Birrel develops a recursive function for searching for a node of a general tree that contains a certain value. She ends with a discussion of four programming practices to avoid. (5:10 minutes) Read it here: searchForNode.pdf

CAUTION: Do not look at the the return type of the function when determining whether it is a counting or a search function. What the function returns has nothing to do it. The determination is based on whether the function should stop when a node with the property is found or whether it should look for more nodes with the property.