Algorithmic Gems — Depth First Order

In this series I talk to computer scientists and software engineers about advanced algorithmic ideas that aren’t typically captured in programming or algorithms textbooks, they reside however in the minds of the top problem solvers and are basically what sets them apart from the rest of the crowd.

Alright, let’s get started. Let’s look at this simple tree structure:

I’ve numbered the nodes in the order they will be visited by a depth first traversal, which basically means that starting from the root at the top we traverse the tree from left to right going deep whenever we can.

Our algorithmic gem for today which I call “Depth First Order” means that as part of the depth first traversal process we record when each node enters and exits the process.

So in our example here the depth first traversal starts at node 1 at time 1. Then at time 2 we enter node 2, we exit node 2 right away at time 3 and enter node 3 at time 4, and so on. Fast forward to cover all nodes and we have the numbers in green indicating when we entered and exited each node.

Now a good question is what does recording enter and exit times of nodes in the Depth First traversal give us? Well, if you look closely at the numbers in green, you will notice that the enter time of each node is less than the enter time of any node in its subtree, similarly the exit time of any node is larger than the exit time of all nodes in its subtree. This means that if we order nodes in one line by their enter times then we can use the enter and exit times of any node to locate a segment on that line that contains only the node’s subtree. For instance node 3 has enter time 4 and exit time 19, if we look up 4 and 19 in the ordered list of nodes by enter time we can locate the marked segment representing node 3’s subtree. Obviously we can use binary search to do the lookups efficiently.

So our gem today — called Depth First Order — allows us to look at a subtree of nodes as a one dimensional segment on a line.

Let’s see an example of how that can be useful. Let’s assign a value to each node in the tree:

I’ve written values in green here, now the question is calculate the sum of all values of nodes in node X’s subtree which are at distance D from the root. For instance the sum of nodes at distance 3 from the root which live in node 8’s subtree is 14. A straightforward approach to answer those queries is to perform a depth first traversal of the subtree of each query and sum all values at the required distance, however this approach becomes very inefficient either in terms of time or space complexity if we need to answer a lot of these queries and if we have many nodes in our tree.

So how can we do better? Yep you guessed right, use today’s gem, the Depth First Order, basically for each level from the root node we need to build a list of nodes at that level sorted by enter time and keep the cumulative sum at each element in the list.

Now to answer the query asking about nodes at level 3 that live in the subtree of node 8 — we can locate node 8’s segment on the level 3 list and subtract the cumulative sums of the segment start and end points to get our answer in a nice logarithmic time.

Alright, that’s all for today, I hope you enjoyed the beauty of today’s algorithmic gem. Would love to hear your comments and feedback. Till next time!