Query a binary tree

Question

I have a Root-Parent-Child binary tree and need to sum and get the child values based on several criteria. I'm not sure whether to use Linq or traverse through the tree. The Linq queries crash (Additional information: Unable to cast object of type 'ID' to type 'Greek') and I don't know how to traverse through the tree and check each parameter. Thanks for any help, or links to sites & books to increase my knowledge. This link helped but I'm still stuck.

public class Node
{
    public List<Node> Children = new List<Node>();
    public Node Parent = null;

    public Node(Node fromParent = null)
    {
        if (fromParent != null)
        {
            Parent = fromParent;
            fromParent.Children.Add(this);
        }
    }
}

public class ID : Node
{
    public int IdNo;
    public int DealNo;
    public string Strategy;
    public ID(int _ID,int _DealNo,string _Strategy) : base(null)
    {
        IdNo = _ID;
        DealNo = _DealNo;
        Strategy = _Strategy;
    }
}

public class Greek : Node
{
    public string LegOrPos;
    public string GreekType;
    public Greek(string _LegOrPos, string _GreekType, Node fromParent = null) : base(fromParent)
    {
        LegOrPos = _LegOrPos;
        GreekType = _GreekType;
    }
}

public class DataPoint : Node
{
    public int DpNo;
    public double Value;
    public DataPoint(int _DpNo, double _Value, Node fromParent = null) : base(fromParent)
    {
        DpNo = _DpNo;
        Value = _Value;
    }
}


public void SimpleTest()
{
    List<Node> MC = new List<Node>();

    // 1st node
    var oID = new ID(23, 2,"Fly");                  // ID,DealNo,Strategy
    var oGreek = new Greek("Leg", "Delta", oID);    //LegOrPos,GreekType
    var oDP = new DataPoint(14, 0.235, oGreek);     //DpNo,Value
    MC.Add(oID);

    // 2nd node
    oID = new ID(25, 5,"BWB");
    oGreek = new Greek("Leg", "Vega", oID);
    oDP = new DataPoint(16, 0.345, oGreek);
    MC.Add(oID);

    // 3rd node
    oID = new ID(31,2,"Fly");
    oGreek = new Greek("Leg", "Delta", oID);
    oDP = new DataPoint(14, 0.456, oGreek);
    MC.Add(oID);

    // use linq or traverse through tree?

    // get total for several parameters
    var Total = MC.Where(x => ((ID)x).DealNo == 2 && ((ID)x).Strategy == "Fly" && ((Greek)x).GreekType == "Delta" && ((DataPoint)x).DpNo == 14)     // should sum 1st and 3rd nodes
        .SelectMany(x => x.Children)
        .Sum(x => ((DataPoint)x).Value);

    // get specific value
    var Val = Convert.ToDouble(MC.Where(x => ((ID)x).IdNo == 23 && ((Greek)x).GreekType == "Delta" && ((DataPoint)x).DpNo == 14)     // should find 1st node
    .SelectMany(x => x.Children)
    .Select(x => ((DataPoint)x).Value).Single());

    // traverse method
    foreach (var objID in MC)
        {
            if (objID.IdNo == 23)     //compile error-IdNo not found
            {
                foreach (Greek objGreek in objID.Children)
                {
                    if (objGreek.GreekType == "Delta")
                    {
                        foreach (DataPoint objDP in objGreek.Children)
                        {
                            if (objDP.DpNo == 14)
                            {
                                double qVal = objDP.Value;
                            }
                        }
                    }
                }
            }
        }
}

as far as I see you don't use the binary tree at all. You just populate your nodes, and add them to your list. Are you sure you want some tree like traversing? Or you just don't know how to traverse through a list too? — Tolga Evcimen, Aug 11 '16 at 05:31
http://stackoverflow.com/questions/18863187/how-can-i-loop-through-a-listt-and-grab-each-item — lakshmi prakasan, Aug 11 '16 at 06:11

Enigmativity · Accepted Answer · 2016-08-11T13:02:09.810

1

The problem you seem to have is that you criteria is impossible.

Take this line: MC.Where(x => ((ID)x).DealNo == 2 && ((ID)x).Strategy == "Fly" && ((Greek)x).GreekType == "Delta" && ((DataPoint)x).DpNo == 14). It is kind of saying that you expect each member of MC to be of type ID, Greek, and DataPoint all at the same time.

Based on your comments it sounds like you need this:

var query =
    from id in MC.OfType<ID>()
    from greek in id.Children.OfType<Greek>()
    from dp in greek.Children.OfType<DataPoint>()
    group dp.Value by new
    {
        id.DealNo,
        id.Strategy,
        greek.LegOrPos,
        greek.GreekType,
        dp.DpNo
    } into gs
    select new
    {
        gs.Key,
        Value = gs.Sum(),
    };

When I run that on your data I get this:

edited Aug 11 '16 at 13:02

answered Aug 11 '16 at 07:40

Enigmativity

113,464
11
89
172

Thanks the traverse now works, can this be easily written as a linq query? Re the total query: I see what you mean about all members of MC being of the same type. Your total query compiles but ``total=0`` which not what I was looking for - I wanted to add ``nodes 1 and 3= 0.235+0.456=0.691`` as a check. – Zeus Aug 11 '16 at 08:32
In your opinion is a n ary tree better than a ``Dictionary,double>``? The latter is easier to code, but seems clumsy and prone to later errors? – Zeus Aug 11 '16 at 08:36
@Zeus - I just translated your existing query to make it "work" - I didn't understand your logic so I couldn't make sure it computed the right result. What is your criteria? – Enigmativity Aug 11 '16 at 10:34
I'm trying to store data in memory in an efficient format and then calculate numerous totals of the values by filtering on different parameters. The query is one of the total results. Node 1 and 3 have the same DealNo(2), GreekType (Delta) and DpNo(14) so the query should find these two values and add them together. A "key" could be seen as ``ID-Strategy-LegOrPos-GreekType-DpNo`` – Zeus Aug 11 '16 at 10:55

Tolga Evcimen · Answer 2 · 2016-08-11T07:20:28.077

0

There are few ways for iterating over a list:

/// regular for
for (int L = 0; L <= MC.Count - 1; L++)
{
    Node oID = MC[L];
    if( oID == null ) continue;

    /// oID is your node that you have added to the list MC 
}

/// foreach
foreach ( var oID in MC.Where(_oID => _oID != null) )
{
    /// oID is your node that you have added to the list MC 
}

No matter which way you went, with the oID we just gathered you can get your children nodes too:

foreach ( Greek oGreek in oID.Children.Where(_oGreek => _oGreek != null) )
{
    /// use oGreeks that you've added to your oID node
    ///

    foreach ( DataPoint oDP in oGreek.Children.Where(_oDP => _oDP != null) )
    {
        /// use oDP's that you've added to your greek node
    }
}

edited Aug 11 '16 at 07:20

answered Aug 11 '16 at 05:45

Tolga Evcimen

7,112
11
58
91

thanks, that makes sense, but I'm getting a compile error when looping to find the node ``ID==23`` - please see updated question. Is there anyway to do this using linq? – Zeus Aug 11 '16 at 06:57
It is probably not a compile error, but runtime error. You should check the objects that you iterate over for nullity. See the updated answer. – Tolga Evcimen Aug 11 '16 at 07:18

Query a binary tree

2 Answers2