Binary Search Trees

Note - The code examples used in this post are located at my GitHub account - Binary Search Trees.

A binary search tree or BST is a node based data structure that contains the following properties in each node -

• A key or value - The item contained within the node that can be used in comparisons.
• A pointer to the left subtree - A reference to the children in its left subtree.
• A pointer to the right subtree - A reference to the children in its right subtree.

Figure 2 - A Binary Search Tree Node.

Each node in the tree comprises of the following properties - 

1. All nodes in its left subtree contain key/values that are smaller than the current key/value that is stored in the node. 
2. All nodes in its right subtree contain key/values that are larger than the current key/value that is stored in the node.
3. If the current node is a right child of its parent, the key/value in the current node will be larger than that of its parent.
4. If the current node is a left child of its parent, the key/value in the current node will be smaller than that of its parent. 

A tree comprised of a single node is still a binary search tree. A larger tree can be formed by joining a bunch of individual nodes together so long as they still abide by the properties that are defined above. For example, the illustration below shows a BST built with 7 individual nodes (numbered 1 through to 7). It is a BST because it still maintains the left/right child and parent relationship properties.

Figure 3 - A Binary Search Tree composed of many individual nodes.

It is called a binary search tree because we can determine if a node exists in the tree by using the steps from a binary search. We will go into more detail about how this works in a followup post.

A BST is seen as a recursive data structure because it uses the same node structure repeatedly to build the tree in addition to all nodes containing the same properties. We can leverage these relationships to allow us to perform some pretty nifty operations on these trees with a small amount of code. 

Data Structure Representation -

The primary data structure in a binary search tree is a node. As mentioned in the introduction, a node contains the key/value, a pointer to its left subtree and a pointer to its right subtree. 

 /**
  * The {@link Node} class.
  * This class is responsible for providing
  * the nodes for a binary search tree.
  * 
  * @author szeyick
  */
  private class Node {
  
 /**
  * The value assigned to the node.
  */
  public int value;
  
 /**
  * Pointer reference to the left subtree.
  */
  public Node leftChild;
  
 /**
  * Pointer reference to the right subtree.
  */
  public Node rightChild;
  
 /**
  * Constructor.
  * @param valueTmp - The value for this node.
  */
  public Node(int valueTmp) {
     value = valueTmp;
     leftChild = null;
     rightChild = null;
  }
 }

Figure 4 - Representation of a BST node in code

Figure 4 is the code representation of the node structure of a BST (shown in Figure 2). In this representation, you'll notice that the node also does not contain a pointer reference to its parent and only to its children. We can add the additional pointer, however depending on the specific need, most of the time it isn't required. 

To those that have been following along, you'll notice that the class representation of a BST's node is very similar to that of a linked list. In fact most of what we've done so far is simply rename the reference pointers from a doubly linked list. The main differences between a BST and a linked list is its structure (tree vs list) and the relationships that the nodes have with their parents and children. 

Binary Search Tree Operations - 

Binary Search Tree's like linked lists, have three main basic operations, search, insertion and deletion. We'll cover the operations over the next few posts, starting with searching.