Effectively remove list of nodes from n-ary tree

Question

I have n-ary tree of game objects. The user randomly selects some objects in a tree and wants to delete. Problem is that some objects are children of the another. It turns out after each deletion of the node inside the hierarchy I must iterate through all selected nodes and remove it. Is the algorithm faster than O (n^2)?

Upd: to make it more clear what I need, I wrote pseudocode:

struct TreeNode
{
    vector<TreeNode*> childs;
};

void removeNodeHierarchy(list<TreeNode*>& nodes, TreeNode *n)
{
    for(TreeNode *child : n->childs())
        removeNodeHierarchy(nodes, child);

    nodes.remove(n); // complexity nodes.size()
    delete n;
}

// The function I'm trying to write 
// Problem: Total complexity = nodes.size() * nodes.size()
void removeNodes(list<TreeNode*>& nodes, TreeNode *root)
{
    while (!nodes.empty()) // complexity nodes.size()
    {
        TreeNode *n = nodes.first();
        removeNodeHierarchy(nodes, n);
    }
}

void main()
{
    TreeNode *tree = ...
    list<TreeNode*> nodes = ...

    removeNodes(nodes, tree);
}

What should happen with children of node when node gets deleted? Are they deleted too? — Photon
Copying (or: rewiting) the tree will costO(N) upto ( N log(N)) Filtering the elements while they are being copied will cost O(1). — wildplasser

Msk Msk · Accepted Answer · 2019-03-17T22:24:30

In order to search that node, it will take you O(n^d), where d is the depth of the tree. So it will be faster if d < 2 which I think will almost never be the case for a big game tree. Are you sure that n from n-ary and O(n^2) are the same symbol?

Effectively remove list of nodes from n-ary tree

1 Answers