Traversing a tree depth-first
This recipe will demonstrate one way to traverse through a tree. The algorithm starts at the root node and continues exploring nodes along the entire length of a branch before going back to explore more shallow nodes.
Since we will examine each node before recursively examining its child nodes, we call this a pre-order traversal. Instead, if we examine each node afterwards, then we call this approach post-order traversal. Anything in-between is an in-order traversal, but naturally, there is no unique in-order traversal for rose trees.
The biggest advantage in using the depth-first approach is the minimal space complexity. Video game AIs often use depth-first approaches in determining the ideal move to take against ...
Get Haskell Data Analysis Cookbook now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
