How do I re-arrange the $node->taxonomy array back into a hierarchical tree?
I don't know of an API function that can do this but the following code should help:

$tid = 4; // Your term id

// Grab all of the parents of this term (including the term itself) 
// in reverse order.
$parents = array_reverse(taxonomy_get_parents_all($tid));

$tree = array();

// Get a reference to the root of the array. This reference will be updated
// in each iteration of the loop to refer to the array of children added to
// the term.
$ref = &amp;$tree; 
foreach ($parents as $term) {
  // Add the current term to the relevant root/children array.
  $ref[$term-&gt;tid] = $term;

  // If the current term is NOT the original child term, we add an array of
  // children to the term and update the array reference to point to it.
  if ($term-&gt;tid != $tid) {
    $term-&gt;children = array();
    $ref = &amp;$term-&gt;children;
  }
}


By the time that loop has run the $tree variable will be a hierarchical representation of the original term's parents, with each child term in the children key of it's parent term object. 

I've only tested this on terms that have a single parent; if you've got terms with multiple parents I think you'll struggle to get this to work.