struct TreeNode { int key; TreeNode *left; TreeNode *right; }; USE THIS FUNCTION

Question

struct TreeNode
{
int key;
TreeNode *left;
TreeNode *right;
};

USE THIS FUNCTION HEADER AND NOTHING ELSE:

void doubleTree(TreeNode *node);

Write a C++ function which does the following operation:

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 function is called on the root of the tree.

NOTE: You should set the new nodes children to NULL and handle the appropriate cases for no or more children

Example:

2
   /
1   3

is changed to...

       2
      /
     2   3
    /   /
   1   3
/
1

For example:

Explanation / Answer

  
struct TreeNode
{
int key;
TreeNode *left;
TreeNode *right;
};

/* UTILITY FUNCTIONS TO TEST doubleTree() FUNCTION */
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct TreeNode* newNode(int data)
{
struct TreeNode* node = (struct TreeNode*)
malloc(sizeof(struct TreeNode));
node->data = data;
node->left = NULL;
node->right = NULL;
  
return(node);
}
  
/* Function to convert a tree to double tree */
void doubleTree(struct TreeNode* node)
{
struct TreeNode* 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;
}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.