Javascript Question posted in
A very good W3school tutorial can be found here.

Traverse over tree type structured data uing JavaScript

I have a data set having parent and nested children in it. The purpose of this data is to traverse over parent to -> child1 to-> Child1Child …..
-> child2 to -> child1 to -> child2 to -> child3
-> child3 -> child4

enter image description here

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 hope I have explained the question well and it is making sense. Suggestions are welcomed.

Tags:

2

Answers


  1. 0

    This looks almost similar to Depth First Search (DFS) on a tree like structure.

    I think for forward direction, your approach is correct. For backward direction, you need to maintain a stack of nodes. If you reach a node without children, then you need to pop it from the stack and visit other remaining children.

    You can do something like this:

    let result = [];
let stack = [];

const handleTree = (tree, count) => {
    count = count || 0;
    if (tree) {
        tree.forEach((t, i) => {
            let deepCopy = {...t};
            delete deepCopy.children;
            const { id, parentId } = deepCopy;
            result.push({ id, isVisited: true, parentId });
            if (t.children) {
                // push current node to stack
                stack.push({node: t, index: i+1});
                // recursively call handleTree for children
                handleTree(t.children, count+1);
            } else {
                // if no children, start backtracking
                while (stack.length > 0) {
                    let top = stack[stack.length - 1]; // peek top of stack
                    if (top.node.children && top.index < top.node.children.length) {
                        // if top node has unvisited children, visit them
                        handleTree([top.node.children[top.index]], count+1);
                        top.index++; // increment index of top node
                    } else {
                        // if no unvisited children, pop from stack
                        stack.pop();
                    }
                }
            }
        });
    }
};
    Login or Signup to reply.
  2. 0

    Some comments on your attempt:

    1. There is no need to clone anything when you destructure into primitives. Also the deletion of children from the clone would not be not needed.
    2. To get the items also added on the way back, just do the same thing (the exact same result.push) as on the way down.
    3. You don’t need i. Your loop variable is the node object that you need.
    4. There isn’t a use for the count in your code.
    5. If every output object gets a 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) {
    for (const node of tree ?? []) {
        // No need to clone when you destructure into primitive values:
        const {id, parentId} = node;
        yield { id, parentId, direction: "down" }; // on the way down
        if (node.children) {
            yield* handleTree(node.children);
        }
        yield { id, parentId, direction: "up" }; // on the way up
    }
}

// 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);
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search