0
\$\begingroup\$

My goals for the algorithm were to use recursion, to avoid mutation, and to decouple the tree walking from the action that we take on each node. My sense is that the result uses mode code is reasonably readable but that it might be unconventional.

Test

Test Data

const nestedPaths: TreeNode = {
  path: '/',
  children:
    [
      {
        path: '/one',
        children: [
          {
            path: '/two',
            children: [
              {
                path: '/three',
              }
            ]
          }
        ]
      },
      {
        path: '/four',
        children: [
          {
            path: '/five',
          },
          {
            path: '/six'
          }
        ],
      }
    ]
};

Test Output

The ... represents the unchanged path and children properties of the original node.

const expected = [
  { fullPath: '/four/six', ... },
  { fullPath: '/four/five', ... },
  { fullPath: '/four', ... },
  { fullPath: '/one/two/three', ... },
  { fullPath: '/one/two', ... },
  { fullPath: '/one', ... },
];

Algorithm

Types

type TreeNode = {
  path: string;
  children?: TreeNode[];
};

type FlatTreeNode = TreeNode & {
  fullPath: string;
};

type FlattenTreeNodeState = {
  previousNode: FlatTreeNode;
  flattenedTree: FlatTreeNode[];
};

Walk Tree Depth First

const walkTreeDepthFirst = <TState>(
  node: TreeNode,
  action: (parent: TreeNode, nextChild: TreeNode, state?: TState) => TState,
  state?: TState): TState | undefined => {

  // Use $state to avoid naming collisions while maintaining a functional approach.
  const traverseChildren = ($state?: TState, next = 0): TState | undefined => {

    // base cases:
    // there is no node
    // the node has no children
    // the node has children, but no next child
    if (!node || !node.children || !node.children[next]) {
      return $state;
    }

    const nextChild = node.children[next];

    $state = action(node, nextChild, $state);

    const $updatedState = walkTreeDepthFirst(nextChild, action, $state);
    return traverseChildren($updatedState, next + 1);
  };

  return traverseChildren(state);
};

Flatten Tree Node

const flattenTreeNode = (
    parentNode: TreeNode, 
    currentNode: TreeNode, 
    state?: FlattenTreeNodeState) : FlattenTreeNodeState => {

  const defaultState = {
    previousNode: {
      path: '/',
      fullPath: '/',
    },
    flattenedTree: []
  };

  const { previousNode, flattenedTree } = state || defaultState;

  const fullPathToParentNode = parentNode.path === previousNode.path
    ? previousNode.fullPath
    : parentNode.path;

  const fullPathToCurrentNode = fullPathToParentNode === '/'
    ? currentNode.path
    : fullPathToParentNode + currentNode.path;

  const currentNodeWithFullPath = {
    ...currentNode,
    fullPath: fullPathToCurrentNode,
  };

  return {
    previousNode: currentNodeWithFullPath,
    flattenedTree: [...flattenedTree, currentNodeWithFullPath],
  }
}

Flatten Tree

const flattenTree = (node: TreeNode) => walkTreeDepthFirst(node, flattenTreeNode);
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.