Tree traversal: find all paths of a non binary tree
Tags: datascience, typescript, gamedev
Published: 2020-03-15 22:44:51

**TLDR; demo and code [here](https://www.typescriptlang.org/play/?target=2&ssl=1&ssc=1&pln=142&pc=49#code/C4TwDgpgBA4gTgQzACwDwBUB8UC8UDeAsAFBRQB2A9gCYQDOAXFAHI0QaYDaAugNwlkI1AOb0mAUREQe-YgF9ZJUJBZsOuKOhJLw0SaI1FSUOpQCucAMYQmdYHACW5YQKjAEcUcFv2nL+drEAPQAVCECIVAAglC0YMDIUABmDnB2bogAbhBpCAA2UA4AtmB5EEUQ5O7ADpTkAHQRUE11rLQAFFS0AJLUPo7OAJRMmZQO1E0Awvll1FB1UBAIlol2EGBNLeQAYpRwANbtw1Cj41MzQovLiTUVbsjQlogA7mVwUHBLK-RQCMl7+0apEiWwAMkskkcRmMJsCoNM8rMris3MVoAlHi83h8vg86L8oGUEEl6s1gVsAMrAdYAIWWh2Op1hUEiCKRzwe5HumIQrxyJmpYCgACN6W5KNyoGBPplamZ8V0IECWUESEkzORLDUFk9eXkACLrBLbVJ2dpGMimCzWXoAGlcwkQKHtxlabBdZDquwOHvm5HBxN9dSptPpJDkTAtJnMVggvX6fgdTuQTHgSDQCHIIEwrjdtAA-ExOmx4wKBsJBrhsEzczsAYWjlWTjDawGkg3Kzhqy3XeQQ2A6ZZ9h2mzX5IyYQRXOrNdquWswO1LBZPlU2nG+mW-BPxlPjGQyJY6ulFb18XgvOgPF4z+arbHS8u4KvgOu7VBHem5INAgeD3mIHzeolxXSpXxLagf2IVw-yCIIoF2DU5j+JIARgg8HCSKBix6ag6HqMpnASKBsAARkrKM-09OsDiAo50LIORfyouCEPMchkMJCEGMKLD2gAQlPPCCMqYQEgonjqLbOioKoqAmOg-cD1YyYsXuOBzGERJcX+A4RUQTVkB41D3naMpgEKDQAAZeEs1AKAg-DCLE5BbIcABqdyJKUv8j3IdIHDoUEEDsGkDJRPAHFwHA8CEpzROIgBaKBSMkqA-JPCCNDizgHG4NKFxwjdBkUHzlPg9BkECqBnhCyU8hCizhXCxJKCwjFdMBKB+xFMMyrIVjgAlaUIFlcwFTYZU5N47DAuC0KWu86b-z7QVB2HYDZOmhS5J2+TXEK+8bUg2QFLVDUtVqLkvCiREAAUEASOgOHNA6Y2O31PxQcNIze60NwTZwk3TVNkw4cNjjscseB4PdD2PCzdT5OAqUemwt2cWG8B4VwMsRygSnMiAHqewHhBh7gNBxxTDyxQ14mQE00mAV6lKOjdfTIL7kE5v11yK3olqopG3lR6l6jAeVkAFyD0LkXm6jbRtKPKzQHnSrF+WQOrPmuS4OsqOY2slMBHuQKbYPgyZKDAEBJSfF8pTN358T+cgIGedKCdKCBqSd4jM2ZFj4LAG37dAqp-ZuCUF16odxRNmU5XxEz9h4o9Cd94mzfwyW6Glzh6iLkWcjFiBuC23zNZR6olVDxdK-khXVtDIdlfT6uy4lm36KUvbv2Yz5gAsLkM596kSeQOhw0CUJwjhAAlX2R7ca9ffxY2-nZiJVWIGdLoWS81+AW8o3Zu1ge++RfuMc-NyhxNjG50H01QTNswhsnYajIeV+5+ohCiHwikPI1I4DtHQoA6AXZFhSHqOzaKeA76uEGPUIoSB2jmncJ4X234mzYK8FBM6xA8YfmTC-FAqB8DjDJnIbAeB8BQMYGQTgPF8Crxwd4KAAByKy3DbTRn+kwbhpFuHyzYRwrwwi+ECPZsIgATGI3mZB2EEN9tI-hgjYzCIAMxKIkWorhIjNFyJ4Yo8RZVVHH2EaI2R710bcIAGz6MsZI9RPDbFaOsMIgA7C4uSVjOEKJMfY3R-iqKBKkTwvRdihE8IACzhL-JE9x3CYleIcQAVjEehbgAjFTMNYa4mhPC+FNwkSU4x5Timbm4Yo6pATCi1L0Q0iJTThGJNack9pCTuFdIPOwyp2T+kqJ6U4vpFjGmVL8ftJS3BiEZUoGUAilBhDtBuvdHOd57Glm4YkgR3NvyDCAA)**
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.

```ts
/**
 * 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.