CareerCup

A non-recursive approach which makes use of BST.
Assuming parent pointers are not given.
The space complexity is O(log N)
Time complexity is O(log N)

LOGIC:
1. If the left child r right child exists, return it.
2. Store all the ancestors of the nodes to be found in an array in top down manner.
3. Start searching for the successor among ancestors in bottom up manner. If the right child of the ancestor exists & its right child is the node whose successor is to be found, we will continue following the path upwards.

preorderSuccessor(root,p)
{
	if(!root || !p)
		return NULL;
	if(p->left)
		return p->left;
	if(p->right)
		return p-right;
	top=-1;
	while(root->data!=p->data)
	{
		arr[++top]=root;
		if(p->data<root->data)
			root=root->left;
		else
			root=root->right;
	}
	for(i=top;i>=0;i--)
        {
                if(arr[i]->right)
                {
                        if(p!=arr[i]->right)
                                return arr[i]->right;
                }
                p=arr[i];
        }	
        return NULL;
}

I have updated my solution along with the link where i have tried it. Its giving correct output for every input.

See complete code here: ideone.com/18tLJ

public void pre_order_successor(Tree tree,int value,int flag)
    {
    	if(tree == null)
    		return;
    	if(tree.element == value)
    		flag = 1;
    	if(flag == 1)
        {
    		System.out.print(tree.element);
                flag = 0;
                return;
         }
    	else
    	{
    		pre_order_successor(tree.left,value,flag);
    		pre_order_successor(tree.right,value,flag);
    	}
    }

call the function with pre_order_successor(root,value,0).... am i right?

struct node *PreOrderSuccessor(struct node *root,struct node *n)
{

        if(!root||!n)
                return NULL;
        if(n->left)
                return n->left;
        else if(!n->left&&n->right)
                return n->right;
        else
        {
                struct node *succ=root;
                while(root)
                {
                        if(n->data>root->data)
                                root=root->right;
                        else if(n->data<root->data)
                        {
                                succ=root;
                                root=root->left;
                        }
                        else
                                break;
                }
                return succ->right;
        }

}

Time Complexity - O(h)
Space Complexity - O(1)

This comment has been deleted.

I hate this binary tree,Damn!! @

To find the preorder successor of a node, locate that node in the tree.. then check if the left of the node is null. If it is not null then print it. Else if, check if the right of node is null. If it is not null then print it. Else print the right of the root.

To find the preorder successor of node u in bst, parent pointer is needed :
if u has left child l the succ(u) = l
else if u has right child r the succ(u) = r
else if u is a left child of its parent then succ(u) is its right sibling
else if u has ancestor v such that v is left child of its parent and has right sibling 'vrs' succ(u) = vrs.
otherwise no successor exists

struct node* pre_succ(struct node* u)
{
    if(!u) 
      return NULL;
    if(u->left)                         // left child exits
      return u->left;
    if(u->right)                     // no left child but has right child
      return u->right;
    while(u!=NULL && u!=u->parent->left)                                   // is a leaf node
    {
           u = u->parent;
    }
    if(u->parent)
      return u->parent->right;    // right sibling of ancestor which is left child of its parent
    return NULL;          // no sucessor
}

void presuccess(bst *r,int skey,int suc)
{
if(r!=NULL)
{
if(suc==1)
{
cout<<"\n\t"<<r->nm;
suc=0;
return;
}
if(r->nm==skey )
{
suc=1;
}
presuccess(r->left,skey,suc);
presuccess(r->right,skey,suc);
}
}

struct node* pre_succ(struct node *root,struct node* u)
{
if(!u)
return NULL;
if(u->left)
return u->left;
if(u->right)
return u->right;
struct node* ptr = root;
struct node* succ = NULL;
while(ptr!=NULL)
{
if(ptr->right != NULL)
{
succ = ptr;
succ->visited = true;
}
if(ptr == u)
break;
if(ptr->ele < u->ele)
ptr = ptr->right;
else
ptr = ptr->left
}
if(succ && succ->visited == false)
return succ
}

pre_succ(node *root,int value)
{

Well, the solution depends on what information we have.
If parent pointers are given, here is the pseudo code:

1. If the left child exists, return it
2. If the right child exists, return it.
3. If both children do not exist, we must backtrack to parent. Two conditions arise:
If the node is the left child of its parent or the node is the right child of the parent.

If the node is the right child of its parent,move upwards until it becomes the left child.
If the node is the left child, move upwards until its parent doesn't have right child.

PreorderSuccessor(p)
{
	if(p->left)
		return p->left
	if(p->right)
		return p->right;
	
	par=p->parent;
	
	while(par && par->right==p)
	{
		p=par;
		par=p->parent;
	}
	
	while(par && par->right==NULL)
		par=par->parent;
	if(par && par->right)
		return par->right;
	return NULL:
		
}

A recursive approach:
I don't think in any way, we are benefitted whether the tree is BST or BT.

preorderSuccessor(root,p)
{
	static Node* prev;
	if(root)
	{
		if(prev==p)
			return root;
		prev=root;
		preorderSuccessor(root->left,p);
		preorderSuccessor(root->right,p);
	}
	return NULL;
}

Here is the logic
1. If there is a left subchild to the given node it is the successor. Terminate
else
2. If there is a rightsubchild to the given node it is the successor. Terminate
else
3. If the node's parent has a unmarked right subchild . It is the successor. Terminate
else
4. Repeat step 3 navigating through parent going up. Mark the parent as marked as we go up.
5. If you are at root of tree with no unmarked right subchild then there is no successor.

Node* pre_order_successor(Node* p)
{
  if(NULL == p) return NULL;
  if(NULL != p->left) return p->left;
  if(NULL != p->right) return p->right;
  while(NULL != p->parent)
  {
    if (p->parent->left == p && NULL != p->parent->right)
       return p->parent->right;
    p = p->parent;
  }
  return NULL;
}

without parent pointer

find(r, u){
	cand = null;
	while(r !=null && r != u){
		if(u < r){
  		if(r.right != null)
    		cand = r.right;
   		r = r.left;
		}
		else{
  		r = r.right;
		}
  }

	if(r==u){
  	if (r.left!= null)
    	return r.left;
  	else if(r.right !=null)
    	return r.right;
   	else return cand;
	}
	return null;
}

int preOrderSucc(TreeNode node) {
		if (node.leftChild != null)
			return node.leftChild.val;
		if (node.rightChild != null)
			return node.rightChild.val;

		// if node is right child of its parent
		// go up till parent becomes left child.
		// If that does not happen, return -1
		if (node == node.parent.rightChild) {
			while ((node.parent != null) && (node == node.parent.rightChild)) {
				node = node.parent;
			}
		}

		if (node == null)
			return -1;

		// if we are here, that means node is now left child of its parent
		// if node is left child of its parent
		TreeNode temp = node.parent;
		while (temp != null) {
			if (temp.rightChild != null)
				return temp.rightChild.val;
			temp = temp.parent;
		}
		return -1;
	}

This code finds preorder successor of the node p in a bst with root t .

bintree *preorder_succ(bintree *t,bintree *p)
 {
    if(p->left)
      return p->left;
    if(p->right)
       return p->right;
    bintree *temp,*prev;
    temp=t;prev=NULL;
    while(temp!=p)
    {
       
       if(p->value < temp->value)
       {
          prev=temp;         
          temp=temp->left;
       }   
       else   
         temp=temp->right;                  
    }             
    if(!prev || !prev->right)
       return NULL;
    return prev->right;

}

Why don't we use BFS like to make each node into a queue by pre-order, and we de-queue one by one, if we find the value in the queue, then the next de-queue value will be pre-order successor.

tree_node *sucessor = NULL;
tree_node * preOrder_sucessor(tree_node * node, int p) {

	if (node->data == p)
		if(sucessor != NULL) return sucessor;
		else return node;
	else sucessor = node;
	
	if (node->left != NULL)
		preOrder_sucessor(node->left, p);
	else preOrder_sucessor(node->right, p);
}

TreeNode* preorder(TreeNode* root, int key)
{
TreeNode* succ=NULL;
while(root)
{
if(key==root->val)
{
if(root->left) return root->left;
else if (root->right) return root->right;
else return succ;
}
else if(key<root-val)
{
if(root->right) succ=root->right;
root=root->left;
}
else root=root->right;

}
return succ;
}