CODEWITHSUNDEEP
c#data-structures
viks
viks

Reputation: 57

Non-binary tree finding leaf nodes (C#)

           Child c1 = new Child();
            c1.name = "c1";
            c1.Isleaf = false;



            Child c2 = new Child();
            c2.name = "c2";
            c2.Isleaf = true;



            Child c11 = new Child();
            c11.name = "c11";
            c11.Isleaf = true;


            Child c12 = new Child();
            c12.name = "c12";
            c12.Isleaf = false;


            Child c121 = new Child();
            c121.name = "c121";
            c121.Isleaf = true;

            c12.Children = new List<Child>() { c121 };
            c1.Children = new List<Child>() { c11, c12 };

            Parent p = new Parent();

            p.name = "P1";

            p.Children = new List<Child>() { c1, c2 };
            List<Child> leaves = new List<Child>();

enter code here

I implemented finding leaves as following using Queue

static public void FindLeavesQueue(Parent p, List<Child> leaves)
{

    if (p.Children == null) return;

    var toVisit = new Queue<Child>(p.Children);

    while (toVisit.Count > 0)
    {
        var current = toVisit.Dequeue();
        if (current.Isleaf)
            leaves.Add(current);

        if (current.Children != null)
        {
            foreach (var child in current.Children)
            {
                if (child.Isleaf)
                    leaves.Add(child);
                else
                {
                    foreach (Child c in child.Children)
                       toVisit.Enqueue(c);
                }

            }

        }

    }

}
enter code here

But in my application this is running very slow. Because tree is really huge and database transactions are involved. What is the best way to have it faster? Thanks

Upvotes: 0

Views: 402

Answers (1)

pm100
pm100

Reputation: 50210

recursive descent is simply and faster, no copy of stuff to queues.

static public void FindLeaves(Parent p, List<Child> leaves)
{

    if (p.Children == null) return;
    foreach(var child in p.Children)
    {
          if(child.IsLeaf)
             leaves.Add(child);
          else
             FindLeaves(child, leaves);
    }

}

Upvotes: 1

Related Questions