#include <iostream>    
using namespace std;    
typedef int Data;    
    
struct Node    
{    
    Node(Data d):data(d){left = right = NULL;};    
    Data data;    
    Node* left;    
    Node* right;  
    Node* parent;   
};  
  
struct ListNode  
{  
    ListNode(Node* n):data(n){next = NULL;};  
    ListNode* next;  
    Node* data;  
};  
    
class Tree    
{    
public:    
    Tree():root(NULL){};    
    Node* root;    
    void insert(Data data, Node* node = NULL)    
    {    
        if(root == NULL)    
        {    
            root = new Node(data);  
            root->parent = NULL;  
            return;    
        }    
        if(node == NULL) node = root;    
        if(data == node->data)    
        {    
            return;    
        } else if(data < node->data) {    
            if(node->left == NULL)    
            {  
                node->left = new Node(data);  
                node->left->parent = node;        
            } else {  
                insert(data, node->left);    
            }  
        } else {    
            if(node->right == NULL)    
            {  
                node->right = new Node(data);   
                node->right->parent = node;   
            } else {  
                insert(data, node->right);    
            }  
        }    
    };  
    void findNext(Node* n)  
    {  
        if(n == NULL) return;  
        if(n->right != NULL)  
        {  
            Node *p = n->right;  
            while(p->left != NULL)  
                p = p->left;  
            cout<<p->data<<endl;  
        } else {  
            if(n->parent == NULL)  
                return;  
            if(n == n->parent->left)  
            {  
                cout<<n->parent->data<<endl;  
            } else {  
                Node* p = n;  
                while(p->parent != NULL && p == p->parent->right)  
                {  
                    p = p->parent;  
                }  
                if(p->parent != NULL)  
                    cout<<p->parent->data<<endl;  
            }  
        }  
    };  
};    
    
int main()    
{    
    Tree tree;    
    tree.insert(5);    
    tree.insert(1);    
    tree.insert(7);    
    tree.insert(4);    
    tree.insert(3);  
    Node *n = tree.root->left->right;  
    cout<<n->data<<endl;  
    tree.findNext(n);  
    system("pause");    
};