Author: mattchung

Example: Badging in & out of the office

Picture an office requiring employees to badge in and out as they enter and exit the premise. We want to keep track of the employees in the building. We also want to be check if a specific employee is currently in the building. Let’s implement a binary search tree to maintain this dataset.

As employees badge in, we insert the Employee object (using the employee ID as the key) into the three. When employees badge out, we remove them from the tree. Occassionally, we search the database asking “Is Employee X currently in this building?”

Tree structure and performance

What do binary search trees offer over other data structures [3] ?

The binary tree data structure elegantly combines the flexibility and benefits of two existing data structures: linked lists and arrays. Linked lists efficiently add and delete nodes, by updating pointers, but inefficiently search. Linked lists require iterating over every node (i.e “from the head of the list”) until the desired node is found. Arrays, on the other hand, are perfect for searching – when taking advantage of the index – but are unsuitable for insertions/deletions. When inserting at a[i], all indexes greater than i must be shifted up; when an item is deleted at a[i], all indexes greater than i must be shifted down.

This table compares the average runtime complexity of the three data structures.

Binary search trees are suitable for specific problems. Binary search trees can be used to solve problems such as runway reservations [3]. Before we dive into the structure and implement the methods, let’s cover some terminology.

Tree Terminology

Here’s a visual representation of a binary search tree.

    15
   /  \
  7    21
 / \
5  10

A tree consists of nodes that are connected by edges. Those lines above represent the edges.

• Path – Walking node to node, along the edges, creates a sequence known as the path.
• Root – The node at the very top of the tree. There is only one root in the tree.
• Parent – Every node, except for the root, has an edge connecting to the node above it.
• Traverse – checking or performing an operation on the node
• Leaf – a node that contains no children
• Level – The number of generations from the root node (level 0). For example, the root’s childrens are at level 1.

Structure & Operations

The structure of a tree is straight forward. It contains a reference to its root node, which is an instance of the Node class. TheNode class contains two references: leftChild, rightChild. The leftChild references a node whos key (i.e “used for comparing”) is less than the current node’s key, and rightChild references a node with a key greater than the current node’s key. This ordering restriction is a property of BSTs, but not all trees.

Here’s some sample code of the data structure:

 public class BinaryTree<E> {
     Node root;

     private class Node<E> {
         int key;
         E data;
         private Node leftChild;
         private Node rightChild;

         @Override
         public String toString(){
             String myString = "<Node [" + this.key + "]>";
             return myString;
         }
     }
}

public Node<E> find(int key){
    Node<E> currentNode = this.root;
    while(currentNode !=null){
        if (currentNode.key == key){
            return currentNode;
        }

        if (key < currentNode.key){
            currentNode = currentNode.leftChild;
        } else {
            currentNode = currentNode.rightChild;
        }
    }

    return currentNode;
}

public void insert(int key, E data){
    Node<E> newNode = new Node<E>();
    newNode.key = key;
    newNode.data = data;
    if(root == null){
        root = newNode;
        return;
    }else{
        Node<E> currentNode = root;
        Node<E> parent;
        while(true){
            parent = currentNode;
            if(key < currentNode.key){
                currentNode = currentNode.leftChild;
                if (currentNode == null){
                    parent.leftChild = newNode;
                    return;
                }
            }else{
                currentNode = currentNode.rightChild;
                if (currentNode == null){
                    parent.rightChild = newNode;
                    return;
                }
            }

        }
    }
}

public void inorder(Node<E> localRoot){

    if(localRoot !=null){
        Node<E> currentNode = localRoot;
        inorder(currentNode.leftChild);
        System.out.println(currentNode);
        inorder(currentNode.rightChild);
    }


}

public void preorder(Node<E> localRoot){
    if (localRoot != null){
        Node<E> currentNode = localRoot;
        System.out.println(currentNode);
        preorder(currentNode.leftChild);
        preorder(currentNode.rigthChild);
    }
}

public void postOrder(Node<E> localRoot){
    if (localRoot != null){
        Node<E> currentNode = localRoot;
        postOrder(currentNode.leftChild);
        postOrder(currentNode.rightChild);
        System.out.println(currentNode);
    }
}

 Before               After

    15                  15
   /  \                /  \
  7    21             7    21
 / \                   \
5  10                   10

public boolean delete(int key){
    Node<E> currentNode = root;
    Node<E> parent = currentNode;
    boolean isLeftChild = false;

    while (currentNode.key != key){
        parent = currentNode;
        if (key < currentNode.key){
            isLeftChild = true;
            currentNode = currentNode.leftChild;
        } else {
            currentNode = currentNode.rightChild;
        }
        // node not found
        if (currentNode == null){
            return false;
        }
    }
    // Case 1: No children
    if (currentNode.leftChild == null && currentNode.rightChild == null){
        if (currentNode == root){
            root = null;
            return true;
        }
        else if (isLeftChild){
            parent.leftChild = null;
            return true;
        } else {
            parent.rightChild = null;
            return true;
        }
    }
    return false;
}

     Left child with single left child

    15                15
   /  \              /  \
  7   21            5   21
 /
5

     Left Child with a single right child

    15                15
   /  \              /  \
  7   21            9   21
   \
    9

     Right child with single left child

    15                15
   /  \              /  \
  7    21           7    18
      /
     18

     Right child with single right child

    15                15
   /  \              /  \
  7    21           7    25
         \
          25

if (currentNode.leftChild != null && currentNode.rightChild == null){
    if(currentNode == root){
        root = currentNode.leftChild;
    }
    else if(isLeftChild){
        parent.leftChild = currentNode.leftChild;
    } else {
        parent.rightChild = currentNode.leftChild;
    }
}
else if(currentNode.rightChild != null && currentNode.leftChild == null){
    if (currentNode == root){
        root = currentNode.rightChild;
    }
    else if(isLeftChild){
        parent.leftChild = currentNode.rightChild;
    }
    else {
        parent.rightChild = currentNode.rightChild;
    }
}

    15                15
   /  \              /  \
  7   21            8   21
 / \               / \
5   9             5   9
   /
  8

    15
   /  \
  7   21
 / \
5   9
     \
     12
    /  \
   10   14

public Node<E> getSuccesor(Node<E> toBeDeleted){
Node<E> parentSuccessor = toBeDeleted;
Node<E> successor = toBeDeleted;
Node<E> currentNode = toBeDeleted.rightChild;
while(currentNode.leftChild != null){
    parentSuccessor = successor;
    successor = currentNode;
    currentNode = currentNode.leftChild;
}
if(toBeDeleted.rightChild != successor){
    parentSuccessor.leftChild = successor.rightChild;
    successor.rightChild = toBeDeleted.rightChild;
}
return successor;

Drawbacks

The binary search tree sounds like the dream, so why use an alternative data structure?

My manager shared a story of an interview candidate who inserted a sequence of sorted items into a binary search tree. Pause for a moment and visualize the data structure. What do you get?

A linked list!

This increases the height of the tree and we lose advantage of the O(logn) performance. Binary Search tree is suited best forrandomized keys, not sorted.

Example

public class Employee {
    private int id;
    private String firstname;
    private String lastname;

    public Employee (int employeeid, String firstname, String lastname){
        this.id = employeeid;
        this.firstname = firstname;
        this.lastname = lastname;
    }

    @Override
    public String toString(){
        // < 05: Joe Schmoe >
        String myString = "< " + this.id + " " + this.firstname + " >";
        return myString;
    }

    public static void main(String[] args){
        Employee jboyd = new Employee(15, "jess", "boyd");
        Employee mstreiter = new Employee(7, "myles", "streiter");
        Employee mdavis = new Employee(21, "matt", "davis");
        Employee mmadsen= new Employee(5, "martin", "madsen");
        Employee mchung = new Employee(19, "matt", "chung");

        BinaryTree<Employee> employees = new BinaryTree<Employee>();
        employees.insert(jboyd.id, jboyd);
        employees.insert(mstreiter.id, mstreiter);
        employees.insert(mdavis.id, mdavis);
        employees.insert(mmadsen.id, mmadsen);

        // Is myles in the building?
        // returns true
        System.out.println(employees.find(mstreiter.id));

        // Jess clocks out
        employes.delete(jboyd.id);

        // Is Matt in the building?
        // returns false
        System.out.println(employees.find(mchung.id));

    }
}

Exercises

1. Write a function that verifies that a binary search tree is valid.

    15
   /  \
  7   21
 / \
5   17

Acknowledgements

Thanks to Jess Boyd for correcting my initial draft, Matt Davis for pointing out the drawbacks of BSTs, and Martin Madsen for techniques to make the post more comprehensible.

Footnotes

Example 1

The id built in method returns the object’s memory address. We’ll use this to inspect the memory address for x and ythroughout the examples.

x and y point to the same memory address when they are first assigned.

>>> x = 42
>>> y = x
>>> id(x)
4298172632
>>> id(y)
4298172632

Because the value of x is immutable (e.g INT) and cannot be modified, by definition, a new memory address is allocated when x is modified. But, y‘s memory remains unmodified:

>>> x = x + 1
>>> id(x)
4298172608
>>> id(y)
4298172632
>>>

Example 2

Like Example 1, the memory address starts off the same:

>>> x = [1,2,3]
>>> y = x
>>> id(x)
4299948256
>>> id(y)
4299948256

Now that we are dealing with mutable data types, x can be modified in place and the memory address does not change:

>>> id(x)
4299948256
>>> id(y)
4299948256

Mutable default arguments

This quiz seems trivial but it isn’t. Understanding this will prevent a novice mistake of using mutable default arguments.

>>> def update(x, y=[]):
...     y.append(x)
...     return y
...
>>> list1 = ['a', 'b', 'c']
>>> list2 = [1, 2, 3]
>>> update('d', list1)
['a', 'b', 'c', 'd']
>>> update(4, list2)
[1, 2, 3, 4]
>>> list1
['a', 'b', 'c', 'd']
>>> list2
[1, 2, 3, 4]
>>> update('a')
['a']
>>> list3 = update('b')
>>> list3
['a', 'b']
>>> list4 = update('hello')
>>> list4
['a', 'b', 'hello']