Back To The Basics: The Binary Tree Traversing

In my previous post Back To The Basics: The Binary Tree Insert and Find Operations I described The Binary Tree insert and find operations. In this post I'd like to go over several common algorithms for traversing a Binary Tree. Just like the insert and find operations all of our traversal operations will use recursion.

The first three algorithms deal with returning the tree values in different orders.  For this example we'll simply be printing those values out to System.out. The first algorithm allows us to print the Binary Tree's values in pre-order. Notice that in pre-order our recursive function prints the current node before recursing down it's child nodes. Pre-order has us following the tree top down from the left side of the tree to the right.
public void traversePreOrder(Tree<T> parent) {
if(parent == null)
  return;
System.out.print(parent.data + " ");
  this.traversePreOrder(parent.left);
this.traversePreOrder(parent.right);
}

The second algorithm allows us to print the Binary Tree's values in post-order. Notice that in post-order our recursive function prints the current node after recursing down it's child nodes. Post-order has us following the tree bottom up from the left side of the tree to the right. In post-order the leaf nodes are printing before their parent nodes.
public void traversePostOrder(Tree<T> parent) { if(parent == null)     return;
this.traversePostOrder(parent.left);   this.traversePostOrder(parent.right);
System.out.print(parent.data + " "); } The third algorithm allows us to print the Binary Tree's values in-order. In-order, like it's name suggests, prints the tree from the smallest value to largest value. Notice that for in-order traversal we traverse down the left child nodes, then print the current node value, and finally traverse the right child nodes. We print the current node value after traversing the left child nodes and before traversing the right child nodes because the values on the left side of the tree are always smaller than values on the right side. This is what allows us to print the tree in-order. public void traverseInOrder(Tree<T> parent) { if(parent == null)   return;
this.traverseInOrder(parent.left); System.out.print(parent.data + " ");   this.traverseInOrder(parent.right);
} The fourth algorithm allows us to return the size of the tree. The size is determined by number of items in the tree. This is the simplest of all the traversal algorithms. We simply start with a value of 1 to account for the current node and sum the values of the left and right child nodes. The resulting value will be the number of nodes in the tree. Notice that we must check the left and the right nodes for null.
public int getSize() {
int size = 1;   if(this.left != null)
      size += this.left.getSize();
if(this.right != null)     size += this.right.getSize();
return size; } The fifth algorithm allows us to return the max depth of the tree. The max depth of the tree is really just the height of the tree. The way the max depth is determined is by getting the depth of the left side of the tree and the right side and comparing them. For this algorithm, like the getSize one, we start with a value of 1 to account for the depth of the current level of the tree. public int maxDepth() { int depth = 1;   int leftDepth = (this.left == null) ? 0 : this.left.maxDepth();
int rightDepth = (this.right == null) ? 0 : this.right.maxDepth();   int childDepth = (leftDepth > rightDepth) ? leftDepth : rightDepth;
return depth + childDepth; } The sixth algorithm allows us to return the minimum value in the tree. Unlike the previous 5 algorithms we do not traverse through every node in the tree to find this value. The minimum value in the tree is contained in the left most leaf node. So to find this value we simply need to travel down the left side of the tree until we no longer have any child nodes.
public T minValue() { if(this.left != null)     return this.left.minValue();
return this.data; } Finally, the seventh algorithm allows us to return the maximum value in the tree. This algorithm is just like finding the minimum value except this time we use the right side of the tree. To find the maximum value we simply need to travel down the right side of the tree until we no longer have any child nodes.
public T maxValue() { if(this.right != null)     return this.right.maxValue();
return this.data; }

Back To The Basics: The Binary Tree Insert and Find Operations

In my previous post Back To The Basics: The Binary Tree I described The Binary Tree data structure as well as provided a basic template for the class in Java. In this post we’ll take a look at the insert and find operations.

The insert and find operations on a Binary Search Tree are actually quite similar. They both recurse through the tree starting at a particular node (typically the root) using a similar method to a binary search to find the appropriate place that the node should exist at. Once the appropriate place for the node has been determined the find method will return the node if it exists and the insert method will insert the node into that position if it does not already exist. Both operations take time proportional to the height of the tree.

Let’s first take a look at the insert operation.

public void insert(T newData) { 

        this.insert(this, newData);

}

  

private void insert(Tree<T> parent, T newData) { 

        if(parent.data == null) {

                parent.data = newData; 

                return;

        }

  

        if(newData.compareTo(parent.data) == 0)

                return;

  

        if(newData.compareTo(parent.data) < 0) {

                if(parent.left == null) parent.left = new Tree<T>();
                this.insert(parent.left, newData);

        } else {

                if(parent.right == null) parent.right = new Tree<T>();
                this.insert(parent.right, newData);

        }

}

Now let's take a look at the find operation.

public Tree<T> find(T dataToFind) {

        return this.find(this, dataToFind);

}

private Tree<T> find(Tree<T> parent, T dataToFind) {

        if(parent == null)

                return parent;

        if(parent.data.compareTo(dataToFind) == 0)

                return parent;

        if(dataToFind.compareTo(parent.data) < 0)

                return this.find(parent.left, dataToFind);

        return this.find(parent.right, dataToFind);

}

What you should notice is that these two operations are strikingly similar. They both take advantage of recursion. Both of the algorithms are made up of the same three parts.

The first part of the algorithm checks to see if the current node exists. In the case of the insert operation this is true if the data of the node is null.* If this is true we know that we can safely set the nodes data and exit. In the find operation this is true if the node itself is null in which case we didn't find what we're looking for. In either case this is an exit condition of the recursive calls.

The second part of the algorithm checks to see if the current nodes data is equal to the data passed in to the method. In the case of the insert operation this is a signal that duplicate data is attempting to be inserted into the tree. In this case we can terminate the recursion since we know we no longer have any additional work to do. In the case of the find operation this is the signal that we've found the data that we're looking for so we can return the current node and exit our recursion.

The last part of the algorithm recurses to the next level of the tree. It decides which branch of the tree to recurse down based on whether the data passed in to the method is less or greater than the current nodes value.  This is what allows this algorithm to have time proportional to the height of the tree. Because we only recurse down one child node we're only ever acting on one node at each level of the tree.

* The insert operation needs to set the data on a an existing node and cannot act on a null node. The reason for this is that we'd need a way to create the new node and assign it to the parent. Because we're using recursion this is difficult but easily overcome if before we recurse into the insert operation we first make sure the node we're sending in IS NOT NULL.  

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.

Post Mortems

In my previous post on Continuous Delivery I mentioned using postmortems as a way to share responsibility and create action items to address and prevent failures as part of a change. I thought it would be helpful if I took the time to explain how I like to run postmortem meetings.

To me a good postmortem meeting has five distinct parts. Each part has a goal that's measurable and useful in understanding a failure and preventing that failure from being exhibited in the system again. It's important to go through these parts sequentially and in the order defined below.

Identify what happened

This may seem like common sense, but a good postmortem should always start with a chronological list of the sequence of events. These events should focus on the WHAT and not the WHY or the HOW. The purpose of this part is to get everyone on the same page as to what the sequence of events were that lead up to the incident, happened during the incident, and lead up to the resolution of the incident.

Identify what went wrong during the incident 

After the sequence of events has been identified and everyone understands the WHAT of the incident, it's important to understand what went wrong during those sequence of events. It's extremely important to try to keep this factual. If you can't back it up with data, don't include it. Again, that may sound like common sense but it's very easy to get into a finger pointing argument or start blaming other folks or groups during this part.

It's important to call out things like coordination failures, escalation issues, trouble shooting guide issues, or anything else that impeded resolution of the incident. The main goal of this is to take a constructive look at how the existing processes worked and identify holes or gaps in the process.

Identify what went well

After you've identified what went wrong during the incident it's also very important to identify what went well. This is important from more than just a moral perspective. It's important for the group to come to consensus and understand things that accelerated resolving the incident so that they can be included and continued in future incidents. It's also a good way to recognize the efforts of team members or other product groups that put skin in the game during an incident.

During this part it's important to call out things like issues that were identified by an automated system or that were recognized early by some standard operating procedure. It's also important to call out good coordination between teams, any heroic individual or team efforts, as well as any new mitigation strategies that were created or discovered during the incident.

Bring up what issues have been identified as a result of the incident

The main goal of this part is to analyze the data presented in part one in light of what went well or poorly. During this part you want to clearly identify gaps that need to be filled as a result of this incident. This is not the time to bring up HOW to resolve the issues but simply to identify the issues.

During this part it's important to call out gaps in communication or process around incident status notifications. If holes have been found in the trouble shooting guide this is the right time to bring them up. Other things like team members having incorrect permissions or access problems should come up during this part as should lack of training or improper knowledge of third party (or first party) systems.

Identify actionable improvements

By this point you should have a list of things that can be improved. This list may include process improvements, documentation improvements, or software improvements. It's important during this phase to make those improvements actionable. The goal of this part is to walk out of the postmortem with not just a list of what actions need to be taken, but also who is going to take the action. It's very important that one of the goals of the postmortem is that there is a clear understanding of what changes need to be made and accountability for getting those changes implemented.