InOrder vs PreOrder vs PostOrder

Overview

In-Order, Pre-Order, and Post-Order are the three primary binary tree traversal methods (method as in different ways; not functions) using Depth-First Search (DFS). This blog post will examine these traversal methods and additionally explore how to move data around the tree and collect it from different nodes. If you’re learning about these basic DFS tree traversal methods, then you’re likely to benefit by learning the different ways to pass data around trees (and then collecting that data).

Traversal

The below subheadings describe the three DFS tree traversal methods that are easy to find anywhere. Note that current node is referenced below. The current node is always the only node being processed. DFS algorithms are recursive and sequential. It visits one node at a time. Typically, the node that is passed into the function to begin the processing is the root node of the tree.

In-Order, Pre-Order, and Post-Order DFS mean that your algorithmic logic in your recursive function orders the operations such that:

In Order

1. The function calls itself (recurses) on the left child node of the current node being processed.
2. The function does whatever work that needs to be done.
3. The function calls itself (recurses) on the right child node of the current node being processed.

def dfs(currentNode):
  dfs(currentNode.left)
  # some operations
  dfs(currentNode.right)

Pre Order

1. The function does whatever work that needs to be done.
2. The function calls itself (recurses) on the left child node of the current node being processed.
3. The function calls itself (recurses) on the right child node of the current node being processed.

def dfs(currentNode):
  # some operations
  dfs(currentNode.left)
  dfs(currentNode.right)

Post Order

1. The function calls itself (recurses) on the left child node of the current node being processed.
2. The function calls itself (recurses) on the right child node of the current node being processed.
3. The function does whatever work that needs to be done.

def dfs(currentNode):
  dfs(currentNode.left)
  dfs(currentNode.right)
  # some operations

Note: Nothing is stopping you from running these algorithms in reverse (right followed by left).

Passing Values Around The Tree

There’s nothing special about the traversal methods above, but it is interesting to consider how we can use them to pass data around the tree, and to collect it at any node in the tree.

Passing Values Down

Passing values down a tree is done by passing them through the arguments of the recursive function when calling it on the left or right child nodes.

def dfs(currentNode, depth):
  # some operations
  dfs(currentNode.left, depth + 1)
  dfs(currentNode.right, depth + 1)

Passing Values Up

Passing values up a tree is done by returning them from the recursive DFS function. Values can be collected at any node in a tree from its subtree to perform any operation. A target node’s subtree is any node that could exist under it as if the target node were a root. This is typically only something you do with Post-Order traversal, In-Order traversal, or a combination of both where work is done after the left node returns, and more work is done after the right node returns. In this way, you can pass values up from a node in any subtree to its sub-root (i.e. root of a subtree).

def dfs(currentNode):
  # some operations
  leftVal = dfs(currentNode.left) if currentNode.left else 0
  rightVal = dfs(currentNode.right) if currentNode.right else 0
  return currentNode.val + leftVal + rightVal

Passing Values According to DFS Order

Passing values up a subtree is just one way to collect values from around a tree. There’s nothing stopping you from passing data around a tree according to the DFS order (as mentioned above). In the Conclusion, you find out that there’s another way to traverse a tree other than DFS.

Conclusion

Traversing with DFS is a powerful way to move data around trees. Learning In-Order, Pre-Order, and Post-Order are just the beginning to unlocking secrets of solving problems related to trees. The special part is how you move data and retrieve it from around the tree using these traversal methods.

Beyond DFS, it’s also possible to traverse a tree using Breadth-First Search (BFS):

• Geeks for Geeks (both DFS and BFS).
• Wikipedia - Tree Traversal (BFS).

To be updated with diagrams after blog posts used for LLM training.

Author

Sam Malayek works in Vancouver, using this space to fill in a few gaps. Opinions are his own.

• ← Tail Latency
• DFS Backtracking →