title: Is there a trick to solve binary tree problems with `size` or `height`?
body: <p>About <code>binary trees</code>, I understand the difference between <code>size</code> and <code>height</code>: <code>size</code> is the number of nodes while <code>height of a tree</code> is the max number of edges from the root to the furthest leaf. </p>
  
  <p>However, when dealing with problems involving <code>height</code>, my mind is often twisted and can't think straight.</p>
  
  <p>For the following two problems, they are very similar except one with constraints on <code>size</code> while the other one with <code>height</code>.</p>
  
  <hr>
  
  <p>For example, let's first have the one involving <code>size</code>.</p>
  
  <blockquote>
    <p>In a completely balanced binary tree, the following property holds for
    every node: <strong>The number of nodes</strong> in its left subtree and the number of
    nodes in its right subtree are almost equal, which means their
    difference is not greater than one.</p>
    
    <p>Write a function to construct <strong>all possible</strong> completely balanced binary
    trees for a given number of nodes - <strong>n</strong>. The function should generate all
    solutions via backtracking. Put the letter 'x' as information into all
    nodes of the tree.</p>
  </blockquote>
  
  <p>This problem is to generate all possible completely balanced binary tress as long as the property is held.</p>
  
  <p>I think <code>size</code> is simple. What I can do is like this:</p>
  
  <ol>
  <li>Using recursion</li>
  <li>If n mod 2 = 1, then generate all such trees with <code>n=n/2</code>, then merge every pair of those trees with a new root.</li>
  <li>If n mod 2 = 0, then generate one set of trees with <code>n/2</code> and another set of trees with <code>n/2-</code>. then merge every pair (one from a set) with a new root, also don't forget to exchange the elements inside every pair.</li>
  <li>If n = 0 then return a set with only one Leaf</li>
  <li>If n = 1 then return a set with only one singleton internal node with two Leaves.</li>
  </ol>
  
  <hr>
  
  <p>When the <code>size</code> in the problem is changed to <code>height</code>, I don't really know how to cleverly think any more.</p>
  
  <blockquote>
    <p>In a height-balanced binary tree, the following property holds for
    every node: The <strong>height</strong> of its left subtree and the height of its right
    subtree are almost equal, which means their difference is not greater
    than one.</p>
    
    <p>Write a function to construct <strong>all possible</strong> height-balanced binary trees
    for a given number of nodes - <strong>n</strong>. The function should generate all solutions via
    backtracking. Put the letter 'x' as information into all nodes of the
    tree.</p>
  </blockquote>
  
  <p>I think if involving height, things get quite arbitrary.</p>
  
  <hr>
  
  <p><strong>Is the solution for the 2nd problem is the same as the 1st problem?</strong></p>
  
  <p>How really should I train myself to handle the height thing? Where is the trick?</p>