title: XobotOS: Why does the C# binary tree benchmark use a struct?
body: <p>Curious about the <a href="http://blog.xamarin.com/2012/05/01/android-in-c-sharp/">reputed performance gains</a> in xobotos, I checked out the binary tree <a href="https://github.com/zanew/MonovsDalvik">benchmark code</a>.</p>
  
  <p>The Java version of the <a href="https://github.com/zanew/MonovsDalvik/blob/master/BintreesDalvik/src/bintrees/dalvik/BintreesDalvikActivity.java">binary tree node</a> is:</p>
  
  <pre><code>private static class TreeNode
  {
      private TreeNode left, right;
      private int item;
  }
  </code></pre>
  
  <p>The <a href="https://github.com/zanew/MonovsDalvik/blob/master/BintreesMonoDroid/BintreesMonoDroid/BintreesMonodroidActivity.cs">C# version</a> is:</p>
  
  <pre><code>struct TreeNode
  {
    class Next
    {
      public TreeNode left, right;
    }
  
    private Next next;
    private int item;
  }
  </code></pre>
  
  <p>I'm wondering what the benefit of using a struct here is, since the Next and Previous pointers are still encapsulated in a class. </p>
  
  <p>Well, there is one - leaf nodes are pure value types since they don't need left and right pointers. In a typical binary tree where half the nodes are leaves, that means a 50% reduction in the number of objects. Still, the performance gains listed seem far greater.</p>
  
  <p>Question: Is there more to this?</p>
  
  <p>Also, since I wouldn't have thought of defining tree nodes this way in C# (thanks Xamarin!) what other data structures can benefit from using structs in a non-obvious way? (Even though that's a bit off-topic and open ended.)</p>