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
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