Close
Register
Close Window

Data Structures and Algorithms

Chapter 7 Search Trees

Show Source |    | About   «  7.2. Binary Search Trees   ::   Contents   ::   7.4. Balanced Trees  »

7.3. Binary Tree Guided Information Flow

7.3.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.

Example 7.4.1

An extreme example is finding the minimum value in a BST. A bad solution to this problem would visit every node of the tree. However, we can take advantage of the BST property to avoid visiting most nods in the tree. You know that the values greater than the root are always in the right subtree, and those values less than the root are in the left subtree. Thus, at each node we need only visit the left subtree until we reach a leaf node.

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

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

7.3.2. Binary Search Tree Small Count Exercise

   «  7.2. Binary Search Trees   ::   Contents   ::   7.4. Balanced Trees  »

nsf
Close Window