# Binary search trees

## Table of contents

## Binary search trees

In order to achieve better runtime to implement `contains`

using a binary tree, we’ll reintroduce **binary search trees**. Previously, we saw how binary search trees arose from adapting binary search to a sorted linked list.

Sortedness is a key property of binary search trees. The iterator for `TreeSet`

and `TreeMap`

performs an in-order traversal of the binary search tree! For this to work, each node must obey a few critical properties. Mathematicians and computer scientists call these properties **invariants**.

- Binary search tree invariant
- For every non-empty node in a binary search tree:
- All elements in its left subtree are less than the node’s
`data`

. - All elements in its right subtree are greater than the node’s
`data`

. - The left and right subtrees are also binary search trees.

- All elements in its left subtree are less than the node’s

This definition is recursive: in a valid binary search tree, each subtree must also meet the binary search tree invariant. By imposing this invariant, we can implement an optimized `contains`

method for `IntSearchTree`

.

```
// pre : Binary search tree invariant.
// post: Returns true if the value is in this tree, false otherwise.
public boolean contains(int value) {
return contains(overallRoot, value);
}
private boolean contains(IntTreeNode root, int value) {
if (root == null) {
return false;
} else if (root.data == value) {
return true;
} else if (value < root.data) {
return contains(root.left, value);
} else {
return contains(root.right, value);
}
}
```