Write a C++ function TreeNode* copy_tree(TreeNode* T) that returns a copy of bin

Question

Write a C++ function TreeNode* copy_tree(TreeNode* T) that returns a copy of binary tree T Write a C++ function that returns a new binary tree that is identical to the binary tree t except that every leaf in T now has a left child and a right child whose values are equal to x and y, respectively. For example, invoking expand_leaf (T, 9, 12) on the tree on the left produces the tree on the right. Write a C++function int height (TreeNode* T) that returns the height of the binary tree t. Write a C++ function bool same_tree(TreeNode* T1, TreeNode* T2) that returns true if binary trees T_1 and T_2 are exactly the same (same values, same structure), and returns false otherwise. You may assume that values of tree_item_type can be compared by means of the == operator.

Explanation / Answer

Question 4.

Code

       TreeNode* copy_tree(TreeNode *T)

{

TreeNode *temp = (TreeNode*)malloc(sizeof(TreeNode));

temp = create_copy(T);

}

TreeNode* create_copy(TreeNode *T)

{

if(T == NULL)

{

return T;

}

TreeNode *temp = (TreeNode*)malloc(sizeof(TreeNode));

temp -> data = T -> data ;

temp-> left = create_copy( T->left);

temp->right = create_copy(T->right);

return temp;

}

}

  

Explanation

We have to copy given binary tree.

Assumption:

I have assume the structure of binary tree as follows:

Since we have to copy binary tree. I started with given function copy_tree(). This function will return the root of the required binary tree.

In create copy function I used recursion.

step 1. I create a node called temp;

step 2. Copy the data in temp;

step 3. recursion call to copy the left subtreeof given binary tree.

step 4. recursion call to copy the right subtree of given binary tree.

step 5. It will return the root of the required binary tree.

Explanation of step 5: In recursion call stack is used implicitly for function call.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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