Write an algorithm to find the ‘next’ node (i.e., in-ordersuccessor) of a given node in a binary search tree. You may assume that eachnode has a link to its parent.

CareerCup4.6.cpp

#include <iostream>

struct Node
{
  	int data;
	Node* left;
	Node* right;
	Node* parent;
	Node()
	{
		left=NULL;
		right=NULL;
		parent=NULL;
	}
};

Node* Next(Node*);

int main()
{
	Node* root = new Node();
	root->data=5;
	root->left = new Node();
	root->left->parent = root;
	root->left->data=2;
	root->right = new Node();
	root->right->parent = root;
	root->right->data = 8;
	root->left->right = new Node();
	root->left->right->parent = root->left;
	root->left->right->data=3;
	std::cout<<(Next(root->left->right)->data)<<std::endl;
}

Node* Next(Node* node)
{
	if(node->right!=NULL)
	{
		Node* cur = node->right;
		while(cur->left!=NULL)
		{
			cur=cur->left;
		}
		return cur;
	}
	else
	{
		Node* cur = node->parent;
		if(cur->left==node)
		{
			return cur;
		}
		else
		{
			cur=cur->parent;
			while((cur->parent!=NULL)&&(cur->parent->left!=cur))
			{
				cur = cur->parent;
			}
			return cur;
		}
	}
}