Tell me more ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.

Here's a class I made:

public class ItemTree
{

    public Int32 id { get; set; }

    [JsonProperty(NullValueHandling = NullValueHandling.Ignore)]
    public String text { get; set; }

    [JsonProperty(NullValueHandling = NullValueHandling.Ignore)]
    public List<ItemTree> item { get; set; }

    public int parentId { get; set; }

}

And here's how I use it:

var tree = new ItemTree();
tree.id = 0;
tree.text = "sometext";
tree.item = new List<ItemTree>();

foreach (...)
{
    if (tree.item.Count == 0)
    {
      tree.item.Add(new ItemTree
      {
        id = my_id,
        text = my_name,
        item = new List<ItemTree>(),
        parentId = my_par
      });
    }
    else
    {
      tree.item.Where(x => x.id == my_par)
               .Select(x => x.item)
               .First()
               .Add(new ItemTree 
               {
                 id = my_id,
                 text = my_name,
                 item = new List<ItemTree>(),
                 parentId = my_par
               });
    }
}

And it crashes in the line with the Where clause. the reason it crashes is this: the tree has one item who has a list of items, and my query only checks the first item of the tree, not his children.

How to search in the whole depth of the tree and add an item there?

share|improve this question
Is it possible to provide the excect exheption? – kostas ch. 31 mins ago
@kostasch. Yes. tree.item.Where(x => x.id == my_par) is null and it throws nullPointerException. – petko_stankoski 30 mins ago
Can you explain what the line with the Where is supposed to be doing? It seems that it tries to insert a grandchild on the first child of the item in a roundabout way? – SWeko 29 mins ago
@SWeko it needs to insert a child in the tree. The parent of the child should be the item with id == my_par – petko_stankoski 27 mins ago
So the problem is, find a node in the tree and insert a child? – SWeko 26 mins ago
show 4 more comments

6 Answers

It might be convenient to flatten your tree structure into a list. Some logic will be easier to express if you just have an IEnumerable<ItemTree> that contains all the nodes of your tree. You're not losing any information, since you still have the parent ID on every node.

This is a naturally recursive problem. Using a recursive lambda, try something like:

Func<ItemTree, IEnumerable<ItemTree>> flattener;
flattener = t => new[] { t }
                .Concat(t.item == null 
                        ? Enumerable.Empty<ItemTree>()
                        : t.item.SelectMany(child => flattener(child)));

Note that when you make a recursive Func like this, you must declare the Func separately first.

You could also flatten the list using an iterator-block method:

public static IEnumerable<ItemTree> Flatten(ItemTree node)
{
    yield return node;
    if (node.item != null)
    {
         foreach(var child in node.item)
             foreach(var descendant in Flatten(child)
                 yield return descendant;
    }
}

Either way, once the tree is flattened you can do simple Linq queries over the flattened list to find nodes:

flattener(tree).Where(t => t.id == my_id);
share|improve this answer
+1. Note: since this is a recursively defined lambda, the declaration line is mandatory. Func<...> flattener = ... would not work – SWeko 15 mins ago
I have answered this too. But your answered remembered me the recursive lambdas! So +1! – Kaveh Shahbazian 10 mins ago
And how would I add the new ItemTree object to this? The one that's in the foreach loop, in the else. – petko_stankoski 4 mins ago

You are using First() instead of FirstOrDefault(). You should do something like the following instead.

var item = tree.item.Where(x => x.id == my_par)
           .Select(x => x.item)
           .FirstOrDefault();

if (item != null)
           .Add(new ItemTree 
           {
             id = my_id,
             text = my_name,
             item = new List<ItemTree>(),
             parentId = my_par
           });
share|improve this answer
You don't understand. There must be an item in the tree with id == my_par. The problem here is that I don't search in the whole tree. – petko_stankoski 25 mins ago
  1. You should add a mehod HasId in your ItemTree
  2. The method should implement a recursive search of particulat Id and return answer true or false
  3. use (x => x.HasId(my_par))
share|improve this answer
Isn't that what I wrote in the question? – petko_stankoski 17 mins ago

You will need to recurse the tree somehow. One solution is to make an iterator for the ItemTree object, something like:

public class ItemTree
{
  //simple DFS walk of the tree
  public IEnumerable<ItemTree> GetChildren()
  {
     //no items, stop execution
     if ((item == null) || (item.Count == 0))
       yield break;
     foreach (var child in item)
     {
        //return the child first
        yield return child;
        //no way to yield return a collection
        foreach (var grandchild in child.GetChildren())
        {
           yield return grandchild;
        }
     }
  }
}

Now locating the parent is trivial, something like

var parent = tree.GetChilden().First(c => c.id == my_par);
share|improve this answer
Ok and how would I add the new ItemTree object to the one GetChildren returns? – petko_stankoski 9 mins ago

How to search in the whole depth of the tree?

To search a tree-like data structure, you need to walk the tree, in a recursive manner (not necessarily by using a recursive function; but that's another topic).

This function returns all items that have an id equal to my_par:

static IEnumerable<ItemTree> Search(Int32 my_par, ItemTree tree)
{
    if (tree.id == my_par) yield return tree;

    if (tree.item != null && tree.item.Count > 0)
    {
        var answers = new List<ItemTree>();

        foreach (var i in tree.item)
        {
            answers.AddRange(Search(my_par, i));
        }

        foreach (var a in answers) yield return a;
    }
}

And you can search for those nodes with a specific id (for example 1):

var answers = Search(1, tree);
share|improve this answer
And according to this, how would I change the code in the foreach? – petko_stankoski 15 mins ago
You do not need the foreach anymore. Your answers would be var answers = Search(1, tree);. – Kaveh Shahbazian 12 mins ago
The code in the foreach wasn't just for searching, it was for adding node in the tree. And since ItemTree.Search(folder.fol_par, tree).ToList().Add(new ItemTree doesn't work... – petko_stankoski 10 mins ago
Sorry; then I am mistaken and do not understand your question properly. I'll delete this answer after some minutes that you have read this comment. – Kaveh Shahbazian 8 mins ago

This might help:

public static IEnumerable<T> SelectRecursively<T>(this IEnumerable<T> e,
    Func<T, IEnumerable<T>> memberSelector)
{
    foreach (T item in e)
    {
        yield return item;

        IEnumerable<T> inner = memberSelector(item);

        if (inner != null)
            inner.SelectRecursively(memberSelector);
    }
}

With usage like:

List<ItemTree> tree = GetTree();
List<ItemTree> flattenedTree = tree.SelectRecursively(T => T.Items).ToList();

This will start deep-selection, where you can use other LinQ features, like .Where().

share
And how would I add the new ItemTree object to this? The one that's in the foreach loop, in the else. – petko_stankoski 5 mins ago
@petko_stankoski you just simply get an ItemTree and call the .Items.Add(...) method on the List. – AgentFire 2 mins ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.