Javascript Tree view Search

Question

I'm trying to implement tree view search using JavaScript. I found search filter in treeview useful, but the answer provided there wasn't the expected output in my scenario.

Example input:

[
    {
        "id": 1,
        "templateName": "Item 1",
        "isFolder": "true",
        "children": [
            {
                "id": 2,
                "templateName": "Subitem 1",
                "isFolder": "true",
                "children": [
                    {
                        "id": 3,
                        "templateName": "Misc 1",
                        "isFolder": "true",
                        "children": [
                            {
                                "id": 4,
                                "templateName": "Misc 2"
                            }
                        ]
                    }
                ]
            },
            {
                "id": 5,
                "templateName": "Subitem 2",
                "isFolder": "true",
                "children": [
                    {
                        "id": 6,
                        "templateName": "Misc 3"
                    }
                ]
            }
        ]
    },
    {
        "id": 7,
        "templateName": "Item 2",
        "isFolder": "true",
        "children": [
            {   
                "id": 8,
                "templateName": "Subitem 1",
                "isFolder": "true",
                "children": [
                    {
                        "id": 9,
                        "templateName": "Misc 1"
                    }
                ]
            },
            {
                "id": 10,
                "templateName": "Subitem 8",
                "isFolder": "true",
                "children": [
                    {
                        "id": 11,
                        "templateName": "Misc 4"
                    },
                    {
                        "id": 12,
                        "templateName": "Misc 5"
                    },
                    {
                        "id": 13,
                        "templateName": "Misc 6",
                        "isFolder": "true",
                        "children": [
                            {
                                "id": 14,
                                "templateName": "Misc 7"
                            }
                        ]
                    }
                ]
            }
        ]
    }
]

If I search for Subitem 1, then the expected output is:

[
    {
        "id": 1,
        "templateName": "Item 1",
        "isFolder": "true",
        "children": [
            {
                "id": 2,
                "templateName": "Subitem 1",
                "isFolder": "true",
                "children": [
                    {
                        "id": 3,
                        "templateName": "Misc 1",
                        "isFolder": "true",
                        "children": [
                            {
                                "id": 4,
                                "templateName": "Misc 2"
                            }
                        ]
                    }
                ]
            }
        ]
    },
    {
        "id": 7,
        "templateName": "Item 2",
        "isFolder": "true",
        "children": [
            {   
                "id": 8,
                "templateName": "Subitem 1",
                "isFolder": "true",
                "children": [
                    {
                        "id": 9,
                        "templateName": "Misc 1"
                    }
                ]
            }
        ]
    }
]

But the answer in the referenced Q&A returns objects without children properties.

I tried to modify that answer's code and also I added isFolder props for additional validation for my help. But I cannot make it return the expected output above.

Answer 1

You could do this with a recursive function that copies the tree, but only retaining children that have a deeper match. When a node matches, no deeper recursion is needed, as then the whole subtree below that node remains included.

Here I have used map and a chained filter(Boolean). You could achieve the same with reduce. The map will map nodes to false when there is no match somewhere in the subtree rooted by that node. These false values are then eliminated by filter(Boolean):

function deepFilter(nodes, cb) {
    return nodes.map(node => {
        if (cb(node)) return node;
        let children = deepFilter(node.children || [], cb);
        return children.length && { ...node,  children };
    }).filter(Boolean);
}

const forest = [{"id": 1,"templateName": "Item 1","isFolder": "true","children": [{"id": 2,"templateName": "Subitem 1","isFolder": "true","children": [{"id": 3,"templateName": "Misc 1","isFolder": "true","children": [{"id": 4,"templateName": "Misc 2"}]}]},{"id": 5,"templateName": "Subitem 2","isFolder": "true","children": [{"id": 6,"templateName": "Misc 3"}]}]},{"id": 7,"templateName": "Item 2","isFolder": "true","children": [{"id": 8,"templateName": "Subitem 1","isFolder": "true","children": [{"id": 9,"templateName": "Misc 1"}]},{"id": 10,"templateName": "Subitem 8","isFolder": "true","children": [{"id": 11,"templateName": "Misc 4"},{"id": 12,"templateName": "Misc 5"},{"id": 13,"templateName": "Misc 6","isFolder": "true","children": [{"id": 14,"templateName": "Misc 7"}]}]}]}];

const result = deepFilter(forest, node =>
    node.templateName.includes("Subitem 1")
);

console.log(result);