struct TreeNode int key TreeNode *left TreeNode *right void doubleTree(TreeNode
ID: 3912768 • Letter: S
Question
struct TreeNode int key TreeNode *left TreeNode *right 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: is changed to. 2 For example: Test Result 2 In Order Traversal 1 3 1 1 2 2 3 3Explanation / Answer
#include <iostream>
using namespace std;
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct TreeNode
{
int key;
TreeNode *left, *right;
TreeNode(int key)
{
this->key = key;
left = right = NULL;
}
};
/* Given a binary tree, print its nodes in inorder*/
void printInorder(TreeNode* node)
{
if (node == NULL)
return;
/* first recur on left child */
printInorder(node->left);
/* then print the data of node */
cout << node->key << " ";
/* now recur on right child */
printInorder(node->right);
}
/* create a duplicate node for each node as its left child */
void createDoubleTree(TreeNode* node)
{
/* Last node has reached in the last recursive call */
if (node == NULL)
return;
/*Traverse the tree from root along the left subtree to create duplicate node for each node */
createDoubleTree(node->left);
/* make a temporary pointer to point to the current node's left subtree */
TreeNode *temp=node->left;
/*duplicate the current node and make this newly created duplicate node as left child of the current node */
node->left=new TreeNode(node->key);
/* make the newly created duplicate node's left child as the current node's left subtree */
node->left->left=temp;
/* Once done with left subtree repeat the same process on right subtree of the current node */
createDoubleTree(node->right);
}
int main()
{
TreeNode *root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
cout << " Inorder traversal of binary tree is ";
printInorder(root);
createDoubleTree(root);
cout << " Inorder traversal of binary tree is ";
printInorder(root);
return 0;
}
output:
4 2 5 1 3
Inorder traversal of binary tree is
4 4 2 2 5 5 1 1 3 3
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.