Binary search trees

ed Lesson

Table of contents

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