title: Hashing a Tree Structure
body: <p>I've just come across a scenario in my project where it I need to compare different tree objects for equality with already known instances, and have considered that some sort of hashing algorithm that operates on an arbitrary tree would be very useful.</p>
  
  <p>Take for example the following tree:</p>
  
  <pre>
          O
         / \
        /   \
       O     O
      /|\    |
     / | \   |
    O  O  O  O
            / \
           /   \
          O     O
  </pre>
  
  <p>Where each <code>O</code> represents a node of the tree, is an arbitrary object, has has an associated hash function. So the problem reduces to: given the hash code of the nodes of tree structure, and a known structure, what is a decent algorithm for computing a (relatively) collision-free hash code for the entire tree?</p>
  
  <p>A few notes on the properties of the hash function:</p>
  
  <ul>
  <li>The hash function should depend on the hash code of every node within the tree as well as its position.</li>
  <li>Reordering the children of a node <em>should</em> distinctly change the resulting hash code.</li>
  <li>Reflecting any part of the tree <em>should</em> distinctly change the resulting hash code</li>
  </ul>
  
  <p>If it helps, I'm using C# 4.0 here in my project, though I'm primarily looking for a theoretical solution, so pseudo-code, a description, or code in another imperative language would be fine.</p>
  
  <hr>
  
  <h3>UPDATE</h3>
  
  <p>Well, here's my own proposed solution. It has been helped much by several of the answers here.</p>
  
  <p>Each node (sub-tree/leaf node) has the following hash function:</p>
  
  <pre><code>public override int GetHashCode()
  {
      int hashCode = unchecked((this.Symbol.GetHashCode() * 31 +
          this.Value.GetHashCode()));
      for (int i = 0; i &lt; this.Children.Count; i++)
          hashCode = unchecked(hashCode * 31 + this.Children[i].GetHashCode());
      return hashCode;
  }
  </code></pre>
  
  <p>The nice thing about this method, as I see it, is that hash codes can be cached and only recalculated when the node or one of its descendants changes. (Thanks to vatine and Jason Orendorff for pointing this out).</p>
  
  <p>Anyway, I would be grateful if people could comment on my suggested solution here - if it does the job well, then great, otherwise any possible improvements would be welcome.</p>