Use the following tree node definition TreeNode{ TreeNode* left, *right; Int val

Question

Use the following tree node definition

TreeNode{

TreeNode* left, *right;

Int val;

}

1) Given two binary trees, write a function to check if they are identical or not. By "identical", we mean two treees have exactly th same structure and key values
Void identical(TreeNode *T1, TreeNode * T2)...

2) Given a node in binary search tree say x, design an algorithm to find the in-order successor of node x is the node with the smallest
value greater than node x's value. Note that there is no link pointing back to a node's parent.

Explanation / Answer

Here is the code for the first problem:

void identical(TreeNode *T1, TreeNode * T2)
{
if(identicalHelper(T1, T2))
printf("The trees are identical. ");
else
printf("The trees are NOT identical. ");
}
int identicalHelper(TreeNode *T1, TreeNode *T2)
{
if(T1 == NULL && T2 == NULL)   //If both subtrees are empty.
return 1;                   //Return true.
else if(T1 == NULL || T2 == NULL)   //If one tree is empty and the other is not.
return 0;                    //Return false.
else                           //If no tree is empty.
{
if(T1->item != T2->item)   //If the values at that node for each tree are not same.
return 0;                   //Return false.
//If left tree of both trees are identical, and right tree of both trees are identical, return accordingly.
return identicalHelper(T1->left, T2->left) && identicalHelper(T1->right, T2->right);
}
}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

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