i had a test and i need to find out what is the purpose of the next code:
typedef struct _node* Nodeptr;
typedef struct _node {
int data;
Nodeptr left;
Nodeptr right;
} Node;
int F(Nodeptr root, int value) {
int tmp;
if (root == NULL)
return -1;
if (root->left == NULL && root->right == NULL) {
tmp = root->data;
root->data = value;
return tmp;
}
root->data = F(root->left, root->data);
return F(root->right, value);
}
where you call F(root,root->data)
what is the purpose of the code?
my idea was that the code change the node values in a similar order to InOrderTraversal, but i think its not accurate.
7
This is what the code achieves:
-
Every leaf that has a successor node gets its value swapped with that of its successor node. The successor node of a leaf is the closest node that has that leaf in its left subtree.
-
If there is a leaf without successor node, then its value is set to whatever value was passed as second argument in the top-level call of the function, and the original value of that leaf is returned by that function call. If there is no such leaf (that has no successor node), then the top-level call of the function returns -1.
-
Any node that didn’t get its value updated by the above two mechanisms, receives the value -1. These are internal nodes that don’t have a leaf as predecessor node.
In my humble opinion this seems a strange outcome for a function, and I cannot see how it could be useful: some values are swapped, other values are lost, and if the top-level function passes as second argument root->data as you have indicated, then this value could occur twice in the updated tree. I wonder if this is what the designers of this test really had in mind, or whether they had intended something else.