12.13.1. Binary Tree Guided Information Flow¶

When writing a recursive method to solve a problem that requires traversing a binary tree, we want to make sure that we are visiting the required nodes (no more and no less).

So far, we have seen several tree traversals that visited every node of the tree. We also saw the BST search, insert, and remove routines, that each go down a single path of the tree. Guided traversal refers to a problem that does not require visiting every node in the tree, though it typically requires looking at more than one path through the tree. This means that the recursive function is making some decision at each node that sometimes lets it avoid visiting one or both of its children. The decision is typically based on the value of the current node. Many problems that require information flow on binary search trees are “guided” in this way.

Here is a problem that typically needs to visit more than just a single path, but not all of the nodes.

1 / 12 Settings

<<<>>>

Suppose that you want to write a recursive function named range that, given a root to a BST, a key value min, and a key value max, returns the number of nodes having key values that fall between min and max. Function range should visit as few nodes in the BST as possible. An inefficient solution is shown.

• int range(BSTNode root , int min , int max) {
• if(root == null)
• return 0;
• int result = 0;
• if ((min <= (Integer)root.element()) && (max >= (Integer)root.element()))
• result = result + 1;
• result += range(root.left(), min, max);
• result += range(root.right(), min, max);
• return result;
• }

10

5

35

rt

range(rt, 10, 14)

The range function should be written in a way that avoid traversing this side for the given range.

range(rt, 38, 68)

• int range(BSTNode root , int min , int max) {
• if (root == null)
• return 0;
• int result = 0;
• if ((min <= (Integer)root.element()) && (max >= (Integer)root.element()))
• result = result + 1;
• if (min <= (Integer)root.element())
• result += range(root.left(), min, max);
• if (max > (Integer)root.element())
• result += range(root.right(), min, max);
• return result;
• }

Saving...
Server Error
Resubmit

12.13.2. Binary Search Tree Small Count Exercise¶