CODEWITHSUNDEEP
linq
Carl R
Carl R

Reputation: 8214

LINQ: Select nodes that doesn't have a parent

I have a simple tree structure represented like this:

Node
{
   int Id;
   int ParentId;
   int Name;
}

Using LINQ with a List<Node>, how can I select all nodes that doesn't have a parent in the same list?

Example:

Id  ParentId
1   0
2   1
3   1
4   2
5   4
8   6

In the above table, Nodes with Id 1 and 8 doesn't have a parent in the set.

Upvotes: 0

Views: 151

Answers (4)

manji
manji

Reputation: 47978

var res = nodes.Except(from node in nodes
                       join pnode in nodes
                         on node.ParentId equals pnode.Id
                     select node);

or:

var res = from node in nodes
          join pnode in nodes
          on node.ParentId equals pnode.Id into jnodes
          from jnode in jnodes.DefaultIfEmpty()
          where jnode == null
          select node;

or:

var res = nodes.Where(np => !nodes.Any(n => np.ParentId == n.Id));

Upvotes: 1

aligray
aligray

Reputation: 2832

var items = from n in list
            where list.Count(p => n.ParentId == p.Id) == 0
            select n;

Upvotes: 1

Jon Skeet
Jon Skeet

Reputation: 1500665

I would use:

var parents = new HashSet<int>(nodes.Select(node => node.ParentId));
var orphans = nodes.Where(node => !parents.Contains(node.Id));

You could just use:

var orphans = nodes.Where(node => !nodes.Select(x => x.ParentId)
                                        .Contains(node.Id));

but that would be an O(n2) operation, whereas the first version is O(n) assuming normal hashing efficiency. Obviously if n is small it won't matter much...

Upvotes: 1

Ahmed Magdy
Ahmed Magdy

Reputation: 6030

var ids = list.Select(i => i.Id).ToList();
var result = list.Where(i => !ids.Contains(i.ParentId)).Select(i => i);

EDIT: added .ToList() to insure that Contains work EDIT2: reversed the operation to answer the question right.

Upvotes: 0

Related Questions