Hi there,
I am learning data structure. it's really helpful to find such a excellent project. Thanks for the excellent work.
However, I found this code may not work correctly.
|
root->right = getMax(root->right); |
let's say we have a tree like this
node *root = NULL;
root = insert(root, 100);
root = insert(root, 50);
root = insert(root, 25);
root = insert(root, 12);
root = insert(root, 35);
root = insert(root, 75);
root = insert(root, 58);
root = insert(root, 87);
root = insert(root, 150);
root = insert(root, 125);
root = insert(root, 175);
root = insert(root, 168);
root = insert(root, 180);
When I want to delete 50 from this tree, getMax function returns 25 for the max data of the left subtree of node 50, which should have to be 35. And after I delete 50 from this tree, I used inOrder function to check the updated tree. I got this:
[ 12 ] [ 35 ] [ 25 ] [ 58 ] [ 75 ] [ 87 ] [ 100 ] [ 125 ] [ 150 ] [ 168 ] [ 175 ] [ 180 ]
As you can see, the sequence is not correctly ordered.
I think the correct code for getMax should be:
node *getMax(node *root)
{
// If there's no leaf to the right, then this is the maximum key value
if (root->right == NULL)
return root;
else
// root->right = getMax(root->right);
return getMax(root->right);
}
Correct me if I was wrong, please.