Link Menu Search Expand Document

Binary search trees

ed Lesson

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.

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 ( == value) {
        return true;
    } else if (value < {
        return contains(root.left, value);
    } else {
        return contains(root.right, value);