CareerCup

public class SetInorderSuccessor
{
static Node prev=null;
put_successor(Node node)
{
if(node==null) return ;
put_successor(node.left);
if(prev!=null) prev.next=node;
prev=node;
put_successor(node.right);
}

}

Algorithm:

1. we can solve this problem just by using inorder traversal .
2. in addition to inoreder traversal, just we need one "PrevVisitedNode"  variable to store previously visited node address .  
3. we now current node and previous node, so PrevVisitedNode->Next = Root; 


code:

struct node 
{
	int data;
	struct node *left;
	struct node *right;
	struct node *next;
}

typedef struct node *tnode;

void InorderTraversal(tNode *root, tNode **PrevVisitedNode )
{
	if( root == NULL )
		return;
	
	InorderTravesal(root->left, PrevVisitedNode);

	if( *PrevVisitedNode != NULL )
	{
		*PrevVisitedNode->next = root;  // root is inoder successor to the previously visited node
	}

	*PrevVisitedNode = root; 

	InorderTraversal(root->right, PrevVisitedNode);
}

Well I could not answer correctly at the time of test but the very next morning I did it following way:

public Node findSuccessor(Node root){
        if(null == root || (null == root.right && null == root.left))
            return root;
        if(root.right != null){
            Node temp = root.right;
            while (temp.left != null){
                temp =  temp.left;
            }
            root.next = temp;
        }      
        if(root.left != null){
            Node temp2 = findSuccessor(root.left);
            if(temp2.next == null)
                temp2.next = root;
        }
        
        if(root.right != null){
            Node temp2 = findSuccessor(root.right);
            if(temp2.next == null)
                return temp2;
        }
        return root;
    }

public MMNode traverse(Node node){

if(node ==null)
return null;

if(isLeaf(node))
return MMNode(node,node);

MMNode mmLeft = traverse(node.left);
MMNode mmRight = traverse(node.right);

if(mmLeft != null && mmLeft.max != null)
{
mmLeft.max.next = node;

}

if(mmRight != null && mmRight.min != null)
{
node.next = mmRight.min;

}

min = mmLeft == null ? node : mmLeft . min;
max = mmRight == null ? node : mmRight . max;

return MMNode(min,max);

}

public class MMNode{

Node max;
Node min;

/*

*/
}

public MMNode traverse(Node node){

if(node ==null)
return null;

if(isLeaf(node))
return MMNode(node,node);

MMNode mmLeft = traverse(node.left);
MMNode mmRight = traverse(node.right);

if(mmLeft != null && mmLeft.max != null)
{
mmLeft.max.next = node;

}

if(mmRight != null && mmRight.min != null)
{
node.next = mmRight.min;

}

min = mmLeft == null ? node : mmLeft . min;
max = mmRight == null ? node : mmRight . max;

return MMNode(min,max);

}

public class MMNode{

Node max;
Node min;

/*

*/
}

Algo:
1) Do inorder traversal of tree first and store the address elements in the queue.
2) Dequeue the first element from the queue.
3) Again do inorder traversal of tree and dequeue each element from the queue and make the next pointer point to the address we dequeued.

Since no constraint has been mentioned in the question , so we can use some extra space.
space complexity- O(n)
time complexity - O(n)

If the node has a right node,
then left most of the right node is the inorder successor of the given node..
else,
scale up the parent, and you find a parent whose left node is the node you are currently in then that parent is the inorder successor of the given node..

Do the above for all elements and store it as next....

Pls correct if i m wrong...

/* Logic
 If a node X does not have a right child, then its successor(in the in-order traversal) will be the closest parent P in whose left sub-tree X lies (this parent is parent_left).
If a node X does not have a left child, then its predecessor(in the in-order traversal) will be the closest parent P in whose right sub-tree X lies. (this parent is parent_right).
*/

void PopulateNext(Node root,Node parent_left,Node parent_right)
{
  if(root==null)
      return;

  PopulateNext(root.left,root,parent_right);
 
  if(root.left==null && parent_right!=null)
    parent_right.next=root;

  if(root.right==null)
    root.next=parent_left;

  PopulateNext(root.right,parent_left,root);
 
}

start with PopulateNext(root,null,null)

Is it not Threaded Binary Tree implementation?

code without parent pointer:
call as: CreateThreadedTree(root, 0);

void BST::CreateThreadedTree(NODE* root, NODE* inSucc)
{
    NODE* succ = 0;
    if (root->_left) {
        CreateThreadedTree(root->_left, root);
    }
    
    if (root->_right) {
        CreateThreadedTree(root->_right, inSucc);
    } else {
        root->_right = inSucc;
    }
}

void PutInorderSuccessorForNode(node **root)
{
	if(! *root)
		return;
	static node* r1;
	Put_Inorder_Successor_In_Each_Node(&(*root)->right);
	(*root)->inordersuccessorNode = r1;
	r1 = *root;
	Put_Inorder_Successor_In_Each_Node(&(*root)->left);
}

void PutInorderSuccessorForNode(node **root)
{
	if(! *root)
		return;
	static node* r1;
	PutInorderSuccessorForNode(&(*root)->right);
	(*root)->inordersuccessorNode = r1;
	r1 = *root;
	PutInorderSuccessorForNode(&(*root)->left);
}

search for threaded binary trees !!

inorder(Node n, Node x){
 if (n==null){
 return;
 }
 inorder(n.left,x);
 if (x!=null){
 x.next = n.data;
 } 
 x = n;  
 inorder(n.right,x);
}

void inorder_populate(node *p)
{ static node *temp=NULL;
if(p==NULL)
return;
else
{
inorder_populate(p->right);
p->next=temp;
temp=p;
inorder_populate(p->left);
}
}

void FillNext(Tree *root, Tree *succ)
{
if(root != NULL)
{
FillNext(root->left, root);
if(root->right == NULL)
{
if (succ != NULL && root->data >= succ->data)
root->next = NULL;
else
root->next = succ;
}
FillNext(root->right, succ);

}
}


int _tmain(int argc, _TCHAR* argv[])
{
int arr[] = {50,40,45};

Tree *root = NULL;

for(int i=0; i<3; i++)
root = CreateTree(root, arr[i]);

FillNext(root, root->right);

return 0;
}