DEV Community

Daniel Neveux
Daniel Neveux

Posted on • Updated on

Tree traversal: find all paths of a non binary tree

TLDR; demo and code here
Today I wrote for the n time a depth first tree traversal function to get all the paths of a tree.
I decided to share this one as I think the crawler implementation is quite generic.

It consists in a function which takes a callback each time the crawler reaches a node, a fork or a leaf.

/**
 * A depth first traversal implementation.
 * 
 * onNode(nodeId: string): void
 * Called on each step
 * 
 * onFork(): void
 * Called each time the crawler reaches a fork.
 * 
 * onLeaf(): void
 * Called each time the crawler reaches a leaf. 
 *
 * onStepBack(): void
 * Called when the crawler step back to the previous node.
 */
function crawlDepthFirst({
  sourceId,
  graph,
  onNode,
  onFork,
  onLeaf,
  onStepBack
}: {
  sourceId: string
  graph: Graph<any>
  onNode?: (nodeId: string) => void
  onFork?:() => void
  onLeaf?:() => void
  onStepBack?:() => void
}): void {
  function step(currentNodeId: string): void {
      const nodeIds = getTargetIds({sourceId: currentNodeId, graph})

      onNode?.(currentNodeId)

      // Found a fork
      if (nodeIds.length > 1) {
        onFork?.()
      }

      // Found a leaf
      if (!nodeIds.length) {
        onLeaf?.()
      }

      // Crawl through each fork branch
      for (let i = 0; i < nodeIds.length; i++) {
        const isLastBranch = i === nodeIds.length - 1
        const nodeId = nodeIds[i]
        step(nodeId);

        // This was the last branch of the fork. Step back
        // to previous node.
        if (isLastBranch) {
          onStepBack?.()
        }
      }
  }
  step(sourceId);
}

As a concrete example, I used it to find all the paths in a tree.

I added a state to the crawler wich is a string array. I update this state with the crawler callback on each node, fork, leaf and step back. Here are some implementation details.

  • The array string represents the current path taken by the crawler.
  • When the crawler hits a leaf, it means that this is the end of a path. A copy of the current path is stored as a complete path. Then the path is poped to return to the previous node.
  • If the crawler comes back from the last branch of a node fork, the path is poped to return to the previous node.

Top comments (0)