Porfiriy Porfiriy - 1 month ago 17
C++ Question

Finding the second max element in a binary search tree

I have a problem with finding the second maximum element in a binary search tree.
I do not know why but in some cases my programm crashes or gives incorrect answer (I don't know those cases).
Help me to find a problem in my algorithm in code below. Thank you.

#include <iostream>
using namespace std;
struct Node {
Node* right;
Node* left;
int data;
Node* parent;
};

Node* maximum(Node *root){
if (root -> right)
return maximum(root -> right);
else
return root;
}
void insert(Node *root, Node *a){
if (root -> left && root -> data > a -> data)
return insert(root -> left, a);
if (root -> right && root -> data < a -> data)
return insert(root -> right, a);
if (root -> data > a -> data){
root -> left = a;
a -> parent = root;
}
if (root -> data < a -> data){
root -> right = a;
a -> parent = root;
}
}
int main(){
int j = 0;
int n = 0;
Node *root = new Node;
cin >> j;
if (j != 0) {
root -> data = j;
root -> parent = NULL;
root -> left = NULL;
root -> right = NULL;
} else {cout << "0"; return 0;}
while (true){
cin >> j;
if (j == 0) break;
Node *a = new Node;
a -> data = j;
a -> left = NULL;
a -> right = NULL;
a -> parent = NULL;
insert(root, a);
}
if(!max -> parent)
if (max -> left)
cout << maximum(max -> left) -> data;
else
cout << max -> data;
else
if (max -> left && max -> left > max -> parent)
cout << maximum(max -> left) -> data;
else
cout << max -> parent -> data;

return 0;
}

Answer

In the following code:

Node* max = maximum(root);

if (max->left){
    if (max->parent->data > max->left->data) cout << max->parent->data;
    else cout << max->left->data;
} else
    cout << max->parent->data;

If your max turns out to be root, then max->parent will be NULL. So you should check for NULL condition before testing it on data.

Comments