Create a new duplicate node for each node in a BST

/*

 For each node in a binary search tree,
 create a new duplicate node, and insert
 the duplicate as the left child of the original node.
 The resulting tree should still be a binary search tree.
 So the tree...
    2
   / \
  1   3

 Is changed to...
       2
      / \
     2   3
    /   /
   1   3
  /
 1

*/

void doubleTree(struct node* node) {
  struct node* oldLeft;

  if (node==NULL) return;

  // do the subtrees
  doubleTree(node->left);
  doubleTree(node->right);

  // duplicate this node to its left
  oldLeft = node->left;
  node->left = newNode(node->data);
  node->left->left = oldLeft;
}