Close
Register
Close Window

Data Structures and Algorithms

Chapter 5 Binary Trees

Show Source |    | About   «  5.7. Implementing Tree Traversals   ::   Contents   ::   5.9. Binary Tree Space Requirements (optional)  »

5.8. Information Flow in Recursive Functions

5.8.1. Information Flow in Recursive Functions

Handling information flow in a recursive function can be a challenge. In any given function, we might need to be concerned with either or both of:

  1. Passing down the correct information needed by the function to do its work,

  2. Returning (passing up) information to the recursive function’s caller.

Any given problems might need to do either or both. Here are some examples and exercises.

5.8.1.1. Local

Local traversal involves going to each node in the tree to do some operation. Such functions need no information from the parent (other than a pointer to the current node), and pass no information back. Examples include preorder traversal and incrementing the value of every node by one.

5.8.1.2. Passing Down Information

Slightly more complicated is the situation where every node needs the same piece of information to be passed to it. An example would be incrementing the value for all nodes by some amount. In this case, the value parameter is simply passed on unchanged in all recursive calls.

Many functions need information that changes from node to node. A simple example is a function to set the value for each node of the tree to be its depth. In this case, the depth is passed as a parameter to the function, and each recursive call must adjust that value (by adding one).

5.8.2. Binary Tree Set Depth Exercise

5.8.3. Collect-and-return

Collect-and-return requires that we communicate information back up the tree to the caller. Simple examples are to count the number of nodes in a tree, or to sum the values of all the nodes.

Example 5.9.1

Consider the problem of counting (and returning) the number of nodes in a binary tree. The key insight is that the total count for any (non-empty) subtree is one for the root plus the counts for the left and right subtrees. Where do left and right subtree counts come from? Calls to function count on the subtrees will compute this for us. Thus, we can implement count as follows.

static <E> int count(BinNode<E> root) {
    if (root == null) return 0;  // Nothing to count
    return 1 + count(root.left()) + count(root.right());
}
def count(root):
    if node is None: return 0  # No nodes to count
    return 1 + count(node.left()) + count(node.right())

The following solution is correct but inefficient as it does redundant checks on the left and the right child of each visited node.

static <E> int ineff_count(BinNode<E> root) {
    if (root == null) return 0;  // Nothing to count
    int count = 0;
    if (root.left() != null)
        count += ineff_count(root.left());
    if (root.right() != null)
        count += ineff_count(root.right());
    if (root.left() == null && root.right() == null)
        return 1;
    return 1 + count;
}
def ineff_count(root):
    if root is None: return 0   # Nothing to count
    count = 0
    if root.left() is not None:
        count += ineff_count(root.left())
    if root.right() is not None:
        count += ineff_count(root.right())
    if root.left() is None and root.right() is None:
        return 1
    return 1 + count

When you write a recursive function that returns a value, such as counting the number of nodes in the subtree, you have to make sure that your function actually returns a value. A common mistake is to make a recursive call and not capture the returned value. Another common mistake is to not return a value.

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

5.8.4. Binary Tree Check Sum Exercise

5.8.5. Binary Tree Leaf Nodes Count Exercise

5.8.6. Binary Tree Sum Nodes Exercise

5.8.7. Combining Information Flows

Many functions require both that information be passed in, and that information be passed back. Let’s start with a relatively simple case. If we want to check if some node in the tree has a particular value, that value has to be passed down, and the count has to be passed back up. The downward flow is simple, as the value being checked for never changes. The information passed up has the simple collect-and-return style: Return True if and only if one of the children returns True.

5.8.8. Binary Tree Check Value Exercise

5.8.9. Combination Problems

Slightly more complicated problems combine what we have seen so far. Information passing down the tree changes from node to node. Data passed back up the tree uses the collect-and-return paradigm.

5.8.10. Binary Tree Height Exercise

5.8.11. Binary Tree Get Difference Exercise

5.8.12. Binary Tree Has Path Sum Exercise

   «  5.7. Implementing Tree Traversals   ::   Contents   ::   5.9. Binary Tree Space Requirements (optional)  »

nsf
Close Window