Wednesday, May 11, 2011

Double the tree such that insert new duplicate node for each node using cpp

Problem
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
As with the previous problem, this can be accomplished without changing the root node pointer.
Solution
/*
 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;
}



0 comments:

Post a Comment