title: Randomly generate trees for unit testing
body: <p>I want to randomly generate trees (not BST) for unit testing of my code. I have tried it in a number of ways but somehow after generation of 3 -4 trees there is an exception or code goes into infinite loop. I am using random numbers for edges and node values.<br>
  I have also tried queue approach where I fill up the queue with random numbers and then dequeue nodes and randomly select the old node from the existing items in the queue and then connect this new node.</p>
  
  <p>Does anybody know how to do this in C# in more better and succinct way?</p>
  
  <p>EDIT </p>
  
  <pre><code>public class Tree
  {
      public Node Root { get; private set; }
      public readonly Dictionary&lt;long, Node&gt; Nodes = new Dictionary&lt;long, Node&gt;();
      public readonly Dictionary&lt;string, long&gt; SumDictionary = new Dictionary&lt;string, long&gt;();
  
      public readonly Dictionary&lt;long, long&gt; FDictionary = new Dictionary&lt;long, long&gt;
      {
          {0, 1},
          {1, 1}
      };
  
  
      public long Query(long n)
      {
          long s = 0;
          Dfs();
  
          for (int i = 1; i &lt;= n; i++)
          {
              for (int j = i; j &lt;= n; j++)
              {
                  var lvalue = GetLValue(i, j);
  
                  if (i != j)
                  {
                      lvalue *= 2;
                  }
  
                  s += lvalue;
  
                  if (s &gt;= Mod)
                  {
                      s %= Mod;
                  }
  
              }
          }
  
          return s;
      }
  
      private long GetLValue(int a, int b)
      {
          var key = string.Format("{0}-{1}", a, b);
  
          if (SumDictionary.ContainsKey(key))
          {
              return Fvalue(SumDictionary[key]);
          }
  
          var aKey = string.Format("{0}-{1}", 1, a);
          var bKey = string.Format("{0}-{1}", 1, b);
  
          var sumA = SumDictionary[aKey];
          var sumB = SumDictionary[bKey];
  
          var lca = Lca(a, b);
  
          if (lca != a &amp;&amp; lca != b)
          {
              return Fvalue(sumA + sumB - SumDictionary[string.Format("{0}-{1}", lca, lca)]);
          }
  
  
          long bigSum, smallSum;
  
          if (sumA &gt; sumB)
          {
              bigSum = sumA;
              smallSum = sumB;
          }
          else
          {
              bigSum = sumB;
              smallSum = sumA;
          }
  
          var sumAtoB = bigSum - (smallSum - Nodes[smallSum].Value);
  
          return Fvalue(sumAtoB);
      }
  
      public void AddNode(long a, long b)
      {
          Node nodea, nodeb;
          if (Nodes.ContainsKey(a))
          {
              nodea = Nodes[a];
          }
          else
          {
              nodea = new Node { Value = a };
              Nodes.Add(a, nodea);
          }
  
          if (Nodes.ContainsKey(b))
          {
              nodeb = Nodes[b];
          }
          else
          {
              nodeb = new Node { Value = b };
              Nodes.Add(b, nodeb);
          }
  
          nodea.ReachableNodes.Add(b, nodeb);
          nodeb.ReachableNodes.Add(a, nodea);
  
          if (Root == null)
          {
              Root = nodea;
          }
      }
  
      public long? Lca(int a, int b)
      {
          bool found = false;
          return TraverseForLca(Root, null, a, b, ref found);
      }
  
      private long? TraverseForLca(Node node, Node prev, long a, long b, ref bool found)
      {
          if (node == null)
          {
              return null;
          }
  
          if (node.Value == a)
          {
              return a;
          }
  
          if (node.Value == b)
          {
              return b;
          }
  
  
          long? f = null;
  
          foreach (KeyValuePair&lt;long, Node&gt; reachableNode in node.ReachableNodes)
          {
              var n = reachableNode.Value;
  
              if (prev != null &amp;&amp; n.Value == prev.Value)
              {
                  continue;
              }
  
              long? lca = TraverseForLca(n, node, a, b, ref found);
  
              if (found)
              {
                  return lca;
              }
  
              if (lca != null &amp;&amp; f == null)
              {
                  f = lca;
              }
              else if (lca != null)
              {
                  found = true;
                  return node.Value;
              }
          }
  
          return f;
      }
  
      public void Dfs()
      {
          TravelForDfs(Root, null, 0);
      }
  
      private void TravelForDfs(Node node, Node prev, long recSum)
      {
          if (node == null)
          {
              return;
          }
  
          var key = string.Format("{0}-{1}", prev != null ? prev.Value : node.Value, node.Value);
          var iKey = string.Format("{0}-{1}", node.Value, node.Value);
          var weight = node.Weight;
  
          if (weight &gt;= Mod)
          {
              weight %= Mod;
          }
  
  
          if (!SumDictionary.ContainsKey(iKey))
          {
              SumDictionary.Add(iKey, weight);
          }
  
          weight = recSum + node.Weight;
  
          if (weight &gt;= Mod)
          {
              weight %= Mod;
          }
  
          foreach (KeyValuePair&lt;long, Node&gt; reachableNode in node.ReachableNodes)
          {
              var n = reachableNode.Value;
  
              if (prev != null &amp;&amp; n.Value == prev.Value)
              {
                  if (!SumDictionary.ContainsKey(key))
                  {
                      SumDictionary.Add(key, weight);
                  }
  
                  continue;
              }
  
              if (!SumDictionary.ContainsKey(key))
              {
                  SumDictionary.Add(key, weight);
              }
  
              TravelForDfs(n, node, weight);
          }
      }
  
      public long Fvalue(long n)
      {
          if (n == 1 || n == 0)
          {
              return 1;
          }
  
          long a, b;
  
          if (FDictionary.ContainsKey(n - 1))
          {
              a = FDictionary[n - 1];
          }
          else
          {
              a = Fvalue(n - 1);
  
              if (!FDictionary.ContainsKey(n - 1))
              {
                  FDictionary.Add(n - 1, a);
              }
  
          }
  
          if (FDictionary.ContainsKey(n - 2))
          {
              b = FDictionary[n - 2];
          }
          else
          {
              b = Fvalue(n - 2);
  
              if (!FDictionary.ContainsKey(n - 2))
              {
                  FDictionary.Add(n - 2, b);
              }
  
          }
  
  
          if (!FDictionary.ContainsKey(n))
          {
              FDictionary.Add(n, a + b);
          }
  
  
          var s = a + b;
          if (s &gt;= Mod)
          {
              s %= Mod;
          }
  
          return s;
  
      }
  
  }
  </code></pre>