Binary trees

ed Lesson

Table of contents

• Binary search
• Binary trees
• Traversals

Binary search

This week, we’ll be learning about the fundamental data structure behind Java’s TreeSet and TreeMap implementations: binary search trees (BSTs). In a binary search tree, elements are stored in sorted order. In the worst case, the runtime of binary search tree operations are all in Θ(log₂ N) with respect to the N, the size of the binary search tree.

Binary search trees are very closely related to the binary search algorithm that we introduced earlier for finding the index of a target element in a sorted array. In each iteration of the binary search algorithm, half of the elements under consideration can be discarded, resulting in a logarithmic time algorithm.

Unfortunately, arrays are fixed in size, making it difficult to add new items to a sorted array-based set. Inserting elements into a sorted array will take linear time since we’ll need to copy over all of the elements into a new, sorted array. When we ran into this problem with inserting or removing elements from the beginning of an arrays, we applied a new approach based on linked nodes.

Unfortunately, this doesn’t work well for binary search.

Goal

Develop a data structure that balances fast search with fast insertion and fast removal.

The critical optimization is to change the entry point so that it’s more convenient for binary search. Instead of entering from the beginning of the linked list, maintain a reference to the middle node. In order to access items in the left half of the data structures, flip the direction of the edges and recursively apply this pattern to each sublist.

Binary trees

What we’ve just defined is the basic structure of a binary search tree. However, before we get to working with binary search trees, we’ll start by working with a slightly simpler structure known as a binary tree.

Binary tree

A tree where each node has either 0, 1, or 2 children.

Binary search tree (BST)

A binary tree with the added binary search invariant.

public class IntTree {
    private IntTreeNode overallRoot;

    private static class IntTreeNode {
        public int data;
        public IntTreeNode left;
        public IntTreeNode right;
    }
}

Like linked nodes, binary tree nodes as represented by IntTreeNode follow a recursive definition. A binary tree falls into one of the two categories.

Empty binary tree

The root IntTreeNode is null.

Non-empty binary tree

The root IntTreeNode contains some data, a left subtree, and a right subtree. Each subtree itself a binary tree.

Traversals

While there was an iterative and recursive traversal for linked lists, binary trees are much better suited for recursive traversal since each node can have two children. Similar to recursive linked list traversal, we’ll want to introduce a public/private pair to maintain a reference to the root of the current subtree.

Unlike linked list traversal, there are three ways of traversing a binary tree depending on when the current node and each left and right children are processed. Consider the following IntTree.

Pre-order traversal

Process the current root node then process the left and right children.

public void print() {
    print(overallRoot);
}

private void print(IntTreeNode root) {
    if (root != null) {
        System.out.print(root.data + " ");
        print(root.left);
        print(root.right);
    }
}

17 41 29 9 81 40

In-order traversal

Process the left child, then process the current root node, and then process the right child.

public void print() {
    print(overallRoot);
}

private void print(IntTreeNode root) {
    if (root != null) {
        print(root.left);
        System.out.print(root.data + " ");
        print(root.right);
    }
}

29 41 17 81 9 40

Post-order traversal

Process the left and right children and then process the current root node.

public void print() {
    print(overallRoot);
}

private void print(IntTreeNode root) {
    if (root != null) {
        print(root.left);
        print(root.right);
        System.out.print(root.data + " ");
    }
}

29 41 81 40 9 17