I have a data set having parent and nested children in it. The purpose of this data is to traverse over parent.
1
/ \
2 3
/ \ / \
4 5 6 7
First traverse 1,2,4 Now 4 has no children During back traverse in else part output 4, 2 then it should go to 2, 5
Now, 5 is end. Trace isVisited in parent nodes if any of the child is property isVisited as false.
5,2,1,3
Expected Output:-
1, 2, 4, 2, 5, 2, 1, 3, 6, 3, 7
Once the node end is reached start traversing reverse direction from end of node to start e.g. child2 where other children were left off and were not visited yet.
Data Set in parent child relationship
[
{
"id": 0,
"children": [
{
"id": 3,
"parentId": 0,
"children": [
{
"id": 6,
"parentId": 3,
"children": [
{
"id": 11,
"parentId": 6,
"children": [
{
"id": 10,
"parentId": 11,
"children": [
{
"id": 8,
"parentId": 10,
}
]
}
]
},
{
"id": 9,
"parentId": 6,
"children": [
{
"id": 1,
"parentId": 9,
"children": [
{
"id": 7,
"parentId": 1,
}
]
}
]
},
{
"id": 4,
"parentId": 6,
}
]
}
]
}
]
}
]
let result = [];
const handleTree = ( tree, count) => {
count = count || 0
const tree = _.clone(data);
if( tree ){
tree.forEach( ( t: any, i: string | number ) => {
let deepCopy = _.clone({...t });
delete deepCopy.children;
const { id, parentId } = deepCopy
result.push({ id, isVisited: true, parentId });
if( tree[i].children ){
handleTree(tree[i].children, count+1 )
}else{
//Completed start reading backward
// const getPreviousParent = findParentDetails(tree[i].parentId )
}
})
}
}
How to approach this problem? So far I have been able to read the data in the same direction but, getting some unexpected results while going backward.
I tried using this code but backtrace I am not getting accurate results.
const handleTree = (tree, path = [], visited = new Set() ) => {
let result = [];
let count = 0;
let visitTree = tree
if( tree && tree.length > 0 ){
const tree2 = (tree) => {
if (tree) {
tree.forEach((t, i) => {
count += 1;
let { children, id, parentId, index, ...rest } = t
result.push({ ...t, id, parentId, isVisited: true, sid: count });
tree = updateIsVisited( tree, id, parentId )
path?.push( t.id );
if (t.children) {
tree2(t.children.sort( ( a: any, b: any ) => b.order - a.order ) );
} else {
tree = updateIsVisited( tree, id, parentId )
path.pop();
const res = returnReverseNodesForTraversel( [...path], tree, t.id );
// Here data is not coming correctly
}
});
}
}
return tree2(tree)
}
};
Function For updating status
const updateIsVisited = ( nodesData, id ) => {
return nodesData.map ( ( node: any ) => {
const updatedNode = {
...node,
isVisited: node.id === id ? true : node.isVisited,
children: Array.isArray( node.children )
? updateIsVisitedInNestedObjects( node.children, id )
: []
}
return updatedNode;
})
}
I hope I have explained the question well and it is making sense. Suggestions are welcomed.
Some comments on your attempt:
children from the clone would not be not needed.result.push) as on the way down.i. Your loop variable is the node object that you need.count in your code. But I have added it to the generated elements. The counter better be a single number, than a separate variable for each execution, so to avoid duplicates. You can wrap that single counter in an object to achieve that.visited: true property, then it doesn't really add any useful information.For such a traversal, a generator comes in handy: that way you don't enforce that the results are collected in an array -- you leave it to the caller to decide what to do with the values and whether or not to abort the traversal.
You could also add a property that indicates what the direction was (down or up).
Here is a possible implementation:
// Define a generator
function* handleTree(tree, counter={node: 0}) {
for (const node of tree ?? []) {
// No need to clone when you destructure into primitive values:
const {id, parentId, children} = node;
const current = { id, parentId, direction: "down", ...counter };
counter.node++;
yield current;
if (children) {
yield* handleTree(children, counter);
}
yield {...current, direction: "up" }; // change the direction
}
}
// Your example tree:
const tree = [{"id": 0,"children": [{"id": 3,"parentId": 0,"children": [{"id": 6,"parentId": 3,"children": [{"id": 11,"parentId": 6,"children": [{"id": 10,"parentId": 11,"children": [{"id": 8,"parentId": 10,}]}]},{"id": 9,"parentId": 6,"children": [{"id": 1,"parentId": 9,"children": [{"id": 7,"parentId": 1,}]}]},{"id": 4,"parentId": 6,}]}]}]}];
const result = [...handleTree(tree)]; // Collect into array
console.log(result);