the getMax function in binary search tree may not work correctly #52

New Issue

claunia · 2026-01-29T15:01:58Z

claunia commented

2026-01-29 15:01:58 +00:00

Originally created by @bayegy on GitHub (Jul 12, 2020).

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.
08415b0f16/data_structures/binary_trees/binary_search_tree.c (L65)

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.

Originally created by @bayegy on GitHub (Jul 12, 2020). 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. https://github.com/TheAlgorithms/C/blob/08415b0f165d73f8cdf5443d2183b2b73b748650/data_structures/binary_trees/binary_search_tree.c#L65 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.

claunia closed this issue

2026-01-29 15:01:59 +00:00

claunia commented

2026-01-29 15:01:59 +00:00

@kvedala commented on GitHub (Jul 13, 2020):

There is an active pull-request in C++ for this file https://github.com/TheAlgorithms/C-Plus-Plus/pull/891
It would be very helpful if you can weigh in on both of them.
Thank you for pointing out the possible error.

@kvedala commented on GitHub (Jul 13, 2020): There is an active pull-request in C++ for this file https://github.com/TheAlgorithms/C-Plus-Plus/pull/891 It would be very helpful if you can weigh in on both of them. Thank you for pointing out the possible error.

claunia commented

2026-01-29 15:01:59 +00:00

@kvedala commented on GitHub (Jul 13, 2020):

@liushubin-gitHub it would be great if you can take a look here as well. Thank you.
(PS: The static code checks are not so stringent here as C is a more primitive language than C++ 😄 )

@kvedala commented on GitHub (Jul 13, 2020): @liushubin-gitHub it would be great if you can take a look here as well. Thank you. (PS: The static code checks are not so stringent here as C is a more primitive language than C++ 😄 )

claunia commented

2026-01-29 15:02:01 +00:00

@liushubin-gitHub commented on GitHub (Jul 13, 2020):

@kvedala @bayegy LGTM

@liushubin-gitHub commented on GitHub (Jul 13, 2020): @kvedala @bayegy LGTM

claunia commented

2026-01-29 15:02:03 +00:00

@bayegy commented on GitHub (Jul 15, 2020):

@kvedala
Hi, I am not sure if this will answer your question.
But I think the implementation of function findMaxInLeftST() in binary_search_tree.cpp is correct. it works fine.

I did not read the "active pull-request" thoroughly, but I have tested the function Remove() in binary_search_tree.cpp. It did not work in some cases. For example, If I want to delete 50 from the tree mentioned above, it throws segmentation fault error. I think the possible
correct implementation of Remove() could be:

void Remove(node **p, int x) {
    if ((*p) == NULL) {
        return;
    }
    if ((*p)->val == x) {
        if ((*p)->right == NULL && (*p)->left == NULL) {
            (*p) = NULL;
        } else if ((*p)->right == NULL) {
            (*p) = (*p)->left;
        } else if ((*p)->left == NULL) {
            (*p) = (*p)->right;
        } else {
            int y = findMaxInLeftST((*p)->left);
            (*p)->val = y;
            Remove(&((*p)->left), y);
        }
    } else if (x < (*p)->val) {
        Remove(&((*p)->left), x);
    } else {
        Remove(&((*p)->right), x);
    }
}

If you want to delete a node from a tree, just use:

Remove(&root, x);

This implementation have been tested worked in various situation. Also, correct me if I was wrong, please.

@bayegy commented on GitHub (Jul 15, 2020): @kvedala Hi, I am not sure if this will answer your question. But I think the implementation of function findMaxInLeftST() in [binary_search_tree.cpp](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/data_structures/binary_search_tree.cpp) is correct. it works fine. I did not read the "active pull-request" thoroughly, but I have tested the function Remove() in [binary_search_tree.cpp](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/data_structures/binary_search_tree.cpp). It did not work in some cases. For example, If I want to delete 50 from the tree mentioned above, it throws segmentation fault error. I think the possible correct implementation of Remove() could be: ``` void Remove(node **p, int x) { if ((*p) == NULL) { return; } if ((*p)->val == x) { if ((*p)->right == NULL && (*p)->left == NULL) { (*p) = NULL; } else if ((*p)->right == NULL) { (*p) = (*p)->left; } else if ((*p)->left == NULL) { (*p) = (*p)->right; } else { int y = findMaxInLeftST((*p)->left); (*p)->val = y; Remove(&((*p)->left), y); } } else if (x < (*p)->val) { Remove(&((*p)->left), x); } else { Remove(&((*p)->right), x); } } ``` If you want to delete a node from a tree, just use: `Remove(&root, x);` This implementation have been tested worked in various situation. Also, correct me if I was wrong, please.

claunia commented

2026-01-29 15:02:03 +00:00

@liushubin-gitHub commented on GitHub (Jul 15, 2020):

LGTM.+1
i have fixed it.segment fault is because null pointer check missing

@liushubin-gitHub commented on GitHub (Jul 15, 2020): LGTM.+1 i have fixed it.segment fault is because null pointer check missing

claunia commented

2026-01-29 15:02:03 +00:00

@kvedala commented on GitHub (Jul 15, 2020):

Thank you, @liushubin-gitHub
@bayegy please feel free to create a pull-request with your suggested fixes. Along with the fixes, please update the code with structure and formatting as the other files like this in the repo. Thank you 😄

@kvedala commented on GitHub (Jul 15, 2020): Thank you, @liushubin-gitHub @bayegy please feel free to create a pull-request with your suggested fixes. Along with the fixes, please update the code with structure and formatting as the other files [like this](https://github.com/TheAlgorithms/C/blob/master/numerical_methods/durand_kerner_roots.c) in the repo. Thank you 😄

claunia commented

2026-01-29 15:02:03 +00:00

@kvedala commented on GitHub (Jul 22, 2020):

@bayegy can you review the PR #579 Thanks.

@kvedala commented on GitHub (Jul 22, 2020): @bayegy can you review the PR #579 Thanks.

claunia commented

2026-01-29 15:02:04 +00:00

@bayegy commented on GitHub (Jul 22, 2020):

@kvedala yes, I have reviewed the PR. looks good to me

@bayegy commented on GitHub (Jul 22, 2020): @kvedala yes, I have reviewed the PR. looks good to me

claunia referenced this issue

2026-01-29 15:10:49 +00:00