DFS

I’ve been doing a lot of DFS lately, almost always in a pre-order traversal, like so:

def dfs(node):
	someOperation(node)
 
	explore(node.left)
	explore(node.right)

This is an intuitive way to reason through many solutions: process the current node then traverse to the children.

However, it has occurred to me that there are other orderings of DFS on binary trees. I believe it is imperative to understand the distinction between these types of traversals so you don’t make any false assumptions about the capabilities of DFS.

I last used them when doing various AST traversals for a compiler where some AST nodes needed to have preorder, inorder, or postorder methods for static analysis, code generation, register allocation, etc. Here are the main ones:

• Pre-order: Root -> Left -> Right
• In-order: Left -> Root -> Right
• Post-order: Left -> Right -> Root

In-order Example

def dfs(node):
	explore(node.left)
	someOperation(node)
	explore(node.right)

A great usage of in order is generating a pretty print “true-ordering” from an AST. Think of an expression like 3 + 4, an AST will have the root node be + with the children being 3 and 4. By traversing in-order, we can print "3 + 4" which is a more human readable version of the expression.

Post-order Example

def dfs(node):
	explore(node.left)
	explore(node.right)
	
	someOperation(node)

A great example of this is type checking or otherwise evaluating a binary expression. This is because we want to evaluate the operands first, and only then we apply the operator. For example, in foo() + bar() we have no clue what the value of the two function calls even are, so we should evaluate those first before adding them together.