CareerCup

whts the need of dp here??

1) push all the nodes on a stack as u traverse in an in order fashion

2) pop the top node assign its extra "next" pointer with NULL.

i.e last->next = null;

temp = last;

while((n = pop(theStack))
{
n->next = temp;
temp = n;
}

}

as simple as that!!..

whats DP doing here??

public binaryNode findSuccessor(binaryNode n)
    {
        if(n==root && n.right==null)
        {
            return null;
        }
        if(n.right!=null)
        {
            binaryNode temp=n.right;
            while(temp.left!=null)
            {
                temp=temp.left;
            }
            return temp;
        }
        if(n==n.parent.right && n.right==null)
        {
            binaryNode temp=n.parent;
            while(true)
            {
                if(temp==root)
                {
                     System.out.println("This is the largest element, no successor exists");
                     return null;
                }
                if(temp==temp.parent.left)
                {
                    return temp.parent;
                }
                else
                {
                    temp=temp.parent;
                }
                
            }
           
        }
        if(n==n.parent.left && n.right==null)
        {
            return n.parent;
        }
        return null;
    }
    
    public void inOrderSuccessor(binaryNode b)
    {
        if(b==null)return;
        inOrderSuccessor(b.left);
        System.out.println("Values are "+b.data);
        binaryNode a=findSuccessor(b);
        if(a!=null)
        {
            System.out.println("Successor is "+a.data);
        }
        inOrderSuccessor(b.right);
    }

public Tree inorder(Tree parent, Tree t) {
        if (t ==  null) return null;
        
        Tree last = inorder(parent, t.left);
        if (last == null && parent != null) parent.next = t;
        else last.next = t;
        
        if (t.right == null) return t;
        return inorder(t, t.right);
    }

Using Iteration

1. if node 'n' has a rc, return min from the right subtree.
2. else, start from root and perform a traversal to find the node 'n', also store a candidate node, which is updated when you move to the left subtree.
3. when n is found(assuming that it exists in the tree), return candidate

Code

public node getInorderSuccessor(Node* n, Node* root)
        {
              if(n->right != null)
                       return findMin(n->right);

               Node * y = root;
               candidate = null;

              while(y != n)
                     {
                               if(y->val > n->val)
                                         {
                                                  y = y->left;
                                                  candidate = y;
                                          }
                                 else
                                          {
                                                 y = y->right
                                           }
                      }
              return candidate;

Morris Algorithm should be the answer for this question.

M sure u kove this code...

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);
}
}