# Binary search trees

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

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);
}
}
``````