Tree Climbing: Using Depth First Search and Breadth First Search

Within the scope of tree data structures, traversal, or searching, is a way for users to efficiently visit every node of a tree or graph while usually executing a callback on the node's data. As humans, we could easily see the entire tree and know the values immediately. But how would a machine, which only reads line by line, know what to do? This is where search algorithms come into play.

Trees can be traversed in two main ways: branch by branch, or level by level. These two methods are called Depth First Search (DFS) and Breadth First Search (BFS) respectively. Using one method over the other depends on the shape of your tree. Since DFS works by diving down the length of a branch until you reach the bottom, it is particularly useful on trees with fewer levels. Transversely, BFS is useful on trees where there are fewer children per node.

Depth First Search: Branch by Branch

Just like a real tree, data trees have branches and leaves and roots. When traversing, you climb down a branch until you arrive at a leaf. Then, climb back up the branch until you reach a fork. At this point, travel down that branch until you find a leaf. This process repeats until every node has been visited.

This is good for visualization, but how can we get the computer to accomplish this? We do this by executing three steps:

1. Iterate the data using a callback
2. Check the left child
3. Check the right child

If a child exists, go to step one and repeat the checklist on the child while remembering your spot in the checklist. This order of operations is referred to as DLR, standing for data, left, right.

The order in which the steps are executed also matters when using DFS. There are three different combinations that are useful to mention:

1. Preorder: data is iterated first
2. Inorder: data is iterated between each check of the children
3. Postorder: data is iterated last

With preorder, data is iterated in the order it was visited. Inorder allows us to visit the leftmost node before iteration. This way items will be iterated in order by magnitude. With postorder, the root node is read last because children will always be iterated before the parent.

A neat way to think about DFS is as a stack. When first visiting a node, push it onto the stack. Then execute the checklist on the top of the stack. After all three steps are done, pop it off. By doing this you never lose track of what node you should be on.

depthFirstSearch(callback, node) {
  callback(node.value);
  if (node.left !== null) {
    depthFirstSearch(callback, node.left);
  }
  if (node.right !== null) {
    depthFirstSearch(callback, node.right);
  }
}

By using recursion we can utilize the call stack to keep track of the nodes for us. The recursive call will also hold
our place in the DLR checklist until we reach the end of the branch.

Breadth First Search: Level by Level

Unlike DFS which dives deep into the tree then resurfaces, BFS is more like a cautious swimmer carefully wading his way to the deep end of the pool. First we start in the shallow end -- the root node and its children -- then move deeper and deeper until we hit the bottom.

A simple way to execute this is to make a list of all the items in the order they will be executed. Then it’s as simple as calling an iterator on every node in the list. But what if we have an especially large tree? It would be quite memory intensive to put every node in a list. We can avoid this issue by iterating as we populate the list, using a queue.

Start with a queue consisting of only the root node. Then start a loop in which the children of the head of the queue are enqueued. Then use the iterator on the head and dequeue it. The queue will hold the correct order while minimizing storage.

breadthFirstSearch(callback) {
  const queue = [];
  queue.push(this);
  while (queue.length > 0) {
    const currentNode = queue[0];
    if (currentNode.left !== null) {
      queue.push(currentNode.left);
    }
    if (currentNode.right !== null) {
      queue.push(currentNode.right);
    }
    callback(currentNode.value);
    queue.shift();
  }
}

As you can see the loop will only stop executing once the queue is empty. Meanwhile the head will be checked, (its children being added to the queue), called, and finally dequeued before moving on to the new head.

Time-Space Complexity

The time taken to execute each search increases with the amount of nodes in the tree since every node must be visited once. The memory space taken during BFS increases as the size of the queue does. Therefore the worst case scenario is that every node is in the queue at once. This makes the space complexity linear as well. The space complexity of DFS depends on the amount of recursive calls running at one time. Thus the complexity is linear with respect to the longest branch of the tree.

By comparing the two search algorithms we can see the similarities and also the differences. Stack vs queue, recursion vs loops, width vs length. But the complexities are essentially the same, so it all comes down to situation when choosing which traversal to use.