title: Verify a tree whether it is Binomial tree
body: <p>I believe that for a tree to be a binomial tree, it must satisfy the requirement that a tree of r node has r children. 
  I define my node to be a tuple of rank, element, and a binomial tree list.</p>
  
  <p>I am not sure how to check whether a tree is a binomial tree. All I can think of is to make a recursive function that implements:</p>
  
  <ol>
  <li>If a tree of rank 0 and an empty list, then it is true that it is a binomial tree.</li>
  <li><p>If a tree of rank r, then I somehow need to check whether my tree is consisted of other trees of ranks r-1,r-2,...,0. Am I on the right track here? I am stuck at this point.
  Here is what I have got so far:</p>
  
  <pre><code> let valid_rank (Tree : tree) : bool = 
     let curr_rank = (rank Tree) in
       let rec helper t counter =
         match t with
          |Node(r,x,c) -&gt; (if  r &lt;&gt; (curr_rank - counter) then false
                          else (match c with
                                  |[] -&gt; true
                                  |t1::ts -&gt; helper t1 (counter + 1)))
                           in helper Tree 0
  
   let verify_Bintree (t : tree) : bool = 
     (valid_rank t) 
  </code></pre>
  
  <p>My point here is that in my valid_rank function, when I "match c with..." at the end, I recursively call helper on t1 and not on the rest of the list ts because helper takes in a tree, not a tree list. I am not sure this will work.</p></li>
  </ol>
  
  <p>My purpose here is that for a tree of, say rank 3, then I want to know whether it has all of the subchildren with ranks 2,1,0. If yes, then it is a binomial tree.</p>
  
  <p>Do you think my valid_rank function is flawed? If so, how can I fix my algorithm?
  Thank you.</p>