Deleting items in tree that are not included in path

Question

public class Item
{
    public string ItemName { get; set; }

    public double Value { get; set; }

    public int Id { get; set; }

    public int ParentId { get; set; }

    public List<Item> Children { get; set; } = new();
}

Hello, I have a task to remove all unnecessary items from tree.

My team gives me function that finds an item with given ItemName. For example I use this function with ItemName = "Item 11".

My colleague told me to remove all unnecessary items (marked as red) from the tree. I should get Item 1 which has list that contains only Item 4 which has list that contains only Item 11.

I am looking for a tip how to solve this issue.

My colleague advised me to start iterating from item that I found (Item 11) and use ParentId to go to the beginning of the tree and delete unnecessary items, but I don't how to move this way.

My second approach is to use recursion to create path to the Item 11 and delete all items that don't have proper Id that the path contains, but I have problem how to implement creating the path.

Can you give me an advice and help solve the issue?

Answer 1

I added this recursive method to the Item class:

public bool ContainsElseRemove(Func<Item, bool> condition)
{
    bool result = condition(this);
    foreach (Item child in Children.ToArray()) {
        if (child.ContainsElseRemove(condition)) {
            result = true;
        } else {
            Children.Remove(child);
        }
    }
    return result;
}

Note that ToArray() is required, because we cannot modify the list being iterated.

And for testing purposes also this one:

public void Print(int level = 0)
{
    Console.WriteLine(new String(' ', 4 * level) + ItemName);
    level++;
    foreach (Item child in Children) {
        child.Print(level);
    }
}

Then I created this test tree by also adding a child to "Item 11" to see whether it would be deleted or not.

var tree = new Item {
    ItemName = "Item 1",
    Children = new List<Item> {
        new Item {
            ItemName = "Item 2",
            Children = new List<Item> {
                new Item { ItemName = "Item 5" },
                new Item { ItemName = "Item 6" },
                new Item { ItemName = "Item 7" }
            }
        },
        new Item {
            ItemName = "Item 3",
            Children = new List<Item> {
                new Item { ItemName = "Item 8" },
                new Item { ItemName = "Item 9" }
            }
        },
        new Item {
            ItemName = "Item 4",
            Children = new List<Item> {
                new Item { ItemName = "Item 10" },
                new Item {
                    ItemName = "Item 11",
                    Children = new List<Item> {
                        new Item { ItemName = "Item 14" }
                    }
                },
                new Item { ItemName = "Item 12" },
                new Item { ItemName = "Item 13" }
            }
        }
    }
};

The test:

Console.WriteLine("Before");
tree.Print();

Console.WriteLine();

Console.WriteLine("After");
tree.ContainsElseRemove(i => i.ItemName == "Item 11");
tree.Print();

Prints:

Before
Item 1
    Item 2
        Item 5
        Item 6
        Item 7
    Item 3
        Item 8
        Item 9
    Item 4
        Item 10
        Item 11
            Item 14
        Item 12
        Item 13

After
Item 1
    Item 4
        Item 11

Caveat: "Item 1" will never be removed. It cannot be removed, since it is the root of the tree and therefore has no parent. But as a workaround you could write:

if (!tree.ContainsElseRemove(i => i.ItemName == "Item 11")) {
    tree = null;
}