Back To The Basics: The Binary Tree

I’d like to begin a new series here entitled Back To The Basics where I go over various software data structures that are helpful to understand. I’d like to start the series with a data structure that I’ve been asked about quite often in various interviews i’ve done during my career as a software developer. That data structure is the Binary Tree.

So what exactly is a Binary Tree? The basic concept of a Binary Tree is actually pretty simple. It’s a tree of nodes. Each node consists of some piece of data and pointers to both a right node and a left node. The first node is called the root node as it is at the root of the tree. The left and right nodes are called child nodes (or internal nodes). Nodes that have no children are called leaf nodes (or external nodes).

What’s so special about a Binary Tree? You can do really cool things with them that allow you to optimize your interaction with the data that the tree contains.  For instance, you can create a Binary Search Tree which allows very fast insert and lookup of nodes.

What’s the difference between a Binary Tree and a Binary Search Tree? A plain Binary Tree has no structure or rules around the organization of it’s child or leaf nodes. This fact makes it hard to optimize the tree operations. A Binary Search Tree adds some structure which makes insert and lookup of nodes very fast. The rules that a Binary Search Tree adds are that the left child node must contain a value that is less than it’s parent value and the right search node must contain a value that is greater than its value. So if I had a node with a value of 4 and I wanted to insert a node with a value of 3 it would go in the left child node. But if I wanted to insert a node with a value of 9 it would go in the right child node.

Binary Tree’s allow us to solve a wide variety of complex software problems like making data searchable, representing hierarchical data, and routing algorithms.

So now that we know what a Binary Tree is let’s take a closer look at a some common operations of a Binary Search Tree. For this example I’m going to write our Binary Search Tree in Java.

public class Tree<T extends Comparable<T>> {
private Tree<T> left;
private Tree<T> right;
private T data;

public T getData() { return this.data; }
public Tree<T> getLeft() { return this.left; }
public Tree<T> getRight() { return this.right; }

public Tree() {
this(null);
}

public Tree(T data) {
  this.left = null;
  this.right=null;
  this.data = data;
}
}

The first thing you’ll notice in the definition of our Tree is that I’m making my Tree extend from Comparable<T>. While this doesn’t have anything to do with a Binary Tree per se, doing this will allow us to create a tree that can handle more complex data types. Extending the Tree from Comparable<T> will allow us to keep the Tree simple and cohesive. It forces us to keep the comparison logic out of the tree which would be a very poor place for it to begin with. 

Taking a look at the definition of our tree the first thing you’ll notice are the three private members. Tree<T> left represents our pointer to the left child node. Tree<T> right represents our pointer to the right child node. Finally T data represents the tree’s data.

One other important thing to notice is that I’ve provided two constructors for this Tree. While we don’t inherently need two constructors there is a nice ease of use factor in having them. Having both an empty constructor and a parameterized constructor allows the consumer to initialize an empty tree or one with data right off the bat.

In my next post I’ll take a look at the two most common operations on a Binary Tree, insert and find.