CareerCup

void SetInorderChildren(BSTNode *pNode, BSTNode **lastPrint)
{
if ( !pNode)
return;
SetInorderChildren(pNode->pLChild,lastPrint);
if (*lastPrint)
(*lastPrint)->pInorder = pNode;
(*lastPrint) = pNode;
SetInorderChildren(pNode->pRChild,lastPrint);
return;

}

Good One. There is a small change needed in the program.
We have to store BSTNode* lastPrint in global storage and update we cannot pass in the function. Because the stack will pop the lastPrint Value as you are using recursion.

void MakeInorder(Tree *tree) {
    MakeInorderInternal(tree, NULL);
}

// Makes inorder of tree.
// returns a pointer to node containing the smallest value.
// max is the current candidate for the successor of the largest node
// in the tree rooted at tree.
Tree *min MakeInorderInternal (Tree *tree, Tree *max) {
    if (!tree) return NULL // or throw, depending on contract;
    Tree *min;
    if (tree->left) {
        min = MakeInorderInternal(tree->left, tree); 
               // tree is current candidate for max.
    } else {
        min = tree;
    }
    if (tree->right) {
        tree->successor = MakeInorderInternal(tree->right, max); 
                                         // max does not change.
    } else {
        tree->successor = max;
    }
    return min;
}

call on root as:
traverse(root, NULL);

int traverse(struct Node * n, struct Node * predecessor)
{
    if (n != NULL) {

        if (n->left != NULL) {
            traverse(n->left, predecessor);
        }

        if (predecessor != NULL) {
            predecessor->successor = n;
        }

        if (n->right != NULL) {
            traverse(n->right, n);
        }
    }
}

void MarkInorderSuccessor(TNode *root)
{

if(root!=null && root->left!=null)
root->left->succesor = root;
MarkInorderSuccessor(root->left);
if(root!=null)
root->successor = LeftMostNode(root->right);
MarkInorderSuccessor(root->right);
}

TNode* LeftMostNode(TNode* root)
{
while(root->left!=null)
root = root->left;
return root;
}

Node** setInorder(Node* node, Node** inOrderNode)
{
	if(!node) return;


	if(node->left != NULL)
	{
		leftInorder = setInorder(node->left, inOrderNode);
		*leftInorder = node;
	}
	else
	{
if(inOrderNode != NULL)	
	*inOrderNode = node;

}

	if(node->right != NULL)
	{
		rightInOrder = serInorder(node->right, &node->Inorder);

}
	else
		rightInOrder = &node->Inorder;

}

/*
 * assumeptions: isEmptyStack(), push() and pop() functions are already implemented
 */
void inorder(Node *head)
{
	struct Node *node = head
	struct Node *predecessor = null;
	while(!isStackEmpty || node!=null){
		if(node!=null){
			push(node);
			node = node->left;
		}
		else{
			node = pop();
			if(predecessor != null)
				predecessor->inordersuccessor = node;
			predecessor = node;
			printf("%d",node->data); //only needed if you want to print
			node = node->right;
		}
	}
}

Void SetSucc(Tree *t)
{
if(!t) return;
else
{
SetSucc(t->left);
SetSucc(t->right);
Tree * successor = SUCC(t) //successor of Tree t's value in t's Child
Tree * predecessor = PRE(t) //predecessor of Tree t's value in t's child
t->succ = successor;
if(predecessor)
predecessor->succ = t;
}

}

/// PLS COMMENT ON ALGO

struct node {
int data;
struct node *left,*right;
struct node *succ;
}

inordersucc(root,NULL);

void inordersucc(struct node *node, struct node *prev)
{
if(!node)
return;
if(node->left!= NULL){
inordersucc(node->left,node);
}
node->succ = prev
if(node->right != NULL){
struct node *min = getMinNode(node->right);
node->succ = min;
inordersucc(node->right,prev);
}
}

struct node * getMinNode(struct node *node)
{

while(node->left != NULL){
node = node->left;
}
return node;
}

Hi guys I am not clear why you all are assuming that its a BST or am I missing something ??

void setInOrderSuccessor(Node *root) {
if (!root) {
return;
}

Stack <Node> stack;
Node *curr = root;
boolean done = false;

while (!done) {
if (current) {
// Push it on stack and move to left
stack.push(curr);
curr = curr->left;
} else {
if (stack.isEmpty()) {
done = true;
} else {
curr = s.top(); // Get the top node
s.pop(); // Remove it from stack
if (curr->right == null) {
curr->successor = s.top(); // current top is the successor
} else {
curr->successor = curr->right; // right child is successor
}
// Move to the right side of the tree
curr = curr->right ;
}
}
}
}

<pre lang="" line="1" title="CodeMonkey55292" class="run-this">
</pre><pre title="CodeMonkey55292" input="yes">// C#
// call FindSucc(head, null)

void FindSucc(Node head, Node Succ)
{
if (head)
{
FindSucc(head.Right, Succ);
head.Succ = Succ;
Succ = head;
FindSucc(head.Left, Succ);
}
}


// Please Comment</pre>

<pre lang="" line="1" title="CodeMonkey94989" class="run-this">void inorder(node *root,node *&pre)
{
if(!root) return;
inorder(root->left,pre);
cout<<root->data<<" ";
if(pre) pre->successor=root;
pre=root;
inorder(root->right,pre);
}

node *pre=NULL;
inorder(root,pre);</pre><pre title="CodeMonkey94989" input="yes">
</pre>

isn't it simple:
traverse the tree in any order (in pre or post) and for every node store the successor as the leftmost node in right subtree(if it exist) or the right child (if it has no left child) complexity: n(lgn)*lgn

I think this will work
void succeed(NODEPTR p,NODEPTR *q)
{
if(p!=NULL)
{
succeed(p->right,q);
p->successor=*q;
*q=p;
succeed(p->left,q);
}
}

looks like right threaded binary tree... http: en wikipedia org / wiki / Threaded_binary_tree

My solution : 2 pre-order traversals .

void AddSuccessor( Node root , Node node)
{
if ( node == NULL )
return ;

Node succ = node;
FindSuccessor( root, node.data, succ );

if ( succ == node ) /* No successor */
node.successor = NULL;
else
node.successor = succ ;

AddSuccessor( root, node.left );
AddSuccessor( root, node.right );
}

void FindSuccessor( Node root, int x, Node &succ)
{
if ( root == NULL )
return ;

if ( root.data > x && succ.data != x && root.data - x < succ.data - x )
succ = root ;
if ( root.data > x && succ.data == x )
succ = root ;

FindSuccessor( root.left, x, succ );
FindSuccessor( root.right, x, succ );
}

//reverse inorder will work
void setinrodersucc(node *root)
{
if(!root)
return root;
node *prev = NULL;
return inorder(root, &prev)
}

inorder(node *root, node**prev)
{
if(!root)
return ;
inorder(root->right, prev);
root->next = *prev;
*prev = root;
inorder(root->left, prev)
}
}

The logic is very simple...just do reverse inorder traversal!!!!
sample code
struct node *bst(struct node *root)
{
if(root==NULL)
return null;
else
{
temp=bst(root->right);
q->in_su=temp;
temp=bst(root->left);
temp->in_su=q;
}
}

at last we need to return temp.