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.
Tree traversal is a classic recursive problem. Approaching this with a recursive algortihm will make the whole thing a lot easier, because you don't have to keep track of already visited nodes or keep a stack of nodes still to visit yourself.
That being said, I think, your expected output is inconsistent, ie if you reverse the order of traversal (ie children from right to left instead of left to right) it should give the reversed traveral. For this to be true, your expected outcome is missing 3 1 at the end. Ie you are adding the way back up to the root when you reach the 5 but not when you reach the 7.
Or is this because the 7 is the very last leaf of your tree? So if you have reached the very last leaf node of your tree, you don't want to add the path back to the root to the traversal?
If my first interpretation is correct, it's a simple recursive depth first traversal, with one difference, you print out the parent node before visiting the children and after traversing each child.
If you really do not need the very last route back to the root, you have to keep track on whether one of the ancestor nodes still has unvisited siblings. You only need to add a node after visiting one of its children if either (1) the node itself still has unvisited children or (2) any of its ancestors has unvisited children.
The following snippet shows both approaches.
The first function is just a recursive depth first traversal, where each node is added to the traversal before visiting any of its children. And then added again, after visiting one of its children (if there are any).
The second function is quite similar. The only difference is the additional parameter, which denotes if any of the ancestors of the currently visited node still has unvisited children. Futhermore upon visiting the children, it is determined whether the current child is the last child beeing processed or not.
//////////////////////////////////////////////////////////////////
function traverse1(tree) {
traversal.push(tree.id);
for (let c of tree.children ?? []) {
traverse1(c);
traversal.push(tree.id)
}
}
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
function traverse2(tree, addPostTraversal) {
traversal.push(tree.id);
for (let i = 0; i < (tree.children ?? []).length; i++) {
let notLastChild = i !== tree.children.length - 1;
traverse2(tree.children[i], addPostTraversal || notLastChild);
if (addPostTraversal || notLastChild) traversal.push(tree.id);
}
}
/////////////////////////////////////////////////////////////////
let data = [{
"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 traversal = [];
traverse1(data[0]);
console.log(traversal.join(" "))
traversal = [];
traverse2(data[0]);
console.log(traversal.join(" "))