# 13.2: Searching for values

- Page ID
- 12807

As I explained in the previous exercise, the run time of **findNode** is proportional to the height of the tree, not the number of nodes, because we don’t have to search the whole tree. But for **containsValue**, we have to search the values, not the keys; the BST property doesn’t apply to the values, so we have to search the whole tree.

My solution is recursive:

public boolean containsValue(Object target) { return containsValueHelper(root, target); } private boolean containsValueHelper(Node node, Object target) { if (node == null) { return false; } if (equals(target, node.value)) { return true; } if (containsValueHelper(node.left, target)) { return true; } if (containsValueHelper(node.right, target)) { return true; } return false; }

**containsValue** takes the **target** value as a parameter and immediately invokes **containsValueHelper**, passing the root of the tree as an additional parameter.

Here’s how **containsValueHelper** works:

- The first
`if`

statement checks the base case of the recursion. If**node**is`null`

, that means we have recursed to the bottom of the tree without finding the**target**, so we should return`false`

. Note that this only means that the target did not appear on one path through the tree; it is still possible that it will be found on another. - The second case checks whether we’ve found what we’re looking for. If so, we return
`true`

. Otherwise, we have to keep going. - The third case makes a recursive call to search for
**target**in the left subtree. If we find it, we can return`true`

immediately, without searching the right subtree. Otherwise, we keep going. - The fourth case searches the right subtree. Again, if we find what we are looking for, we return
`true`

. Otherwise, having searched the whole tree, we return`false`

.

This method “visits” every node in the tree, so it takes time proportional to the number of nodes.