# Functional, recursive algorithm for flattening a tree

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