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);