CareerCup

We can keep do a recursive inorder traversal and keep flag to indicate f we have found the value whose successor to be find. Once the value has been found print the next value and return

void findSuccessor(struct node* head, struct node* key, bool & found)
{
if (head == NULL)
return;
findSuccessor(head->left, key, NULL);

if (*found !=False)
{
print( "found it: %d",head->info;
return;
}
if (head==key)
*found = True
findSuccessor(head->right, key, found);
}

In the inorder traversal for a given node, the successor will be the very next node...
Since all the nodes are arranged in increasing order...

Eg : 1 , 2, 5, 6,7,9,10,15.. (Inorder of a BStree)
Successor of 7 is 9..

This works when right subtree of the node for which successor needs to be found is not null.

If the right subtree is not null then find the min of right subtree.

Other wise start from root (since the parent pointer is not given (assumption)
find the first node who is the left child of it's parent and return the parent of that node.



if parent pointer is given then

if right[x] ≠ NIL
then return TREE-MINIMUM (right[x])
y ← p[x]
while y ≠ NIL and x = right[y]
do x ← y
y ← p[y]
return y

If the right subtree is not null then find the min of right subtree.

Other wise start from root (since the parent pointer is not given (assumption)
find the first node who is the left child of it's parent and return the parent of that node.



if parent pointer is given then

if right[x] ≠ NIL
then return TREE-MINIMUM (right[x])
y ← p[x]
while y ≠ NIL and x = right[y]
do x ← y
y ← p[y]
return y

just do the reverse inorder traversal..i.e. right , data(current) , left.. and save the current in a static/global variable.... do recursion.. when current matches the node whoese successor is to be found.. return the value of the static variable...
var=NULL //global variable
successor(current,node)
{
if(node==current)
return var;
successor(current->right,node);
var=current;
successor(current->left,node);
return var;
}

just do the reverse inorder traversal..i.e. right , data(current) , left.. and save the current in a static/global variable.... do recursion.. when current matches the node whoese successor is to be found.. return the value of the static variable...
var=NULL //global variable
successor(current,node)
{
if(node==current)
return var;
successor(current->right,node);
var=current;
successor(current->left,node);
return var;
}

keep a static flag intiliased to 0 ..wen we find the (whose succesor we r to find out)node ...make that flag =1.and continue traversal.wen flag=1 we return that node as the required node(successor)

public void InorderSuccessor(TreeNode root, TreeNode parent)
        {
            if (root.Left != null)
            {
                InorderSuccessor(root.Left, parent);
                TreeNode r = root.left;
                while (r.Successor != null)
                {
                    r = r.Successor;
                }
                r.successor = root;
            }
            else
            {
                if (parent != null)
                    parent.successor = root;

            }

            if (root.right != null)
            {
                InorderSuccessor(root.Right, root);
            }
        }

The succesor of a node in inorder traversal is the parent.

if(node==root)
return node->right->value;
else if(node==root->left || node==root->right)
return root;
else
return(parent(node));

treeNodePtr inorderSucessor(treeNodePtr N) {
        if(N) {
                treeNodePtr tmp;
                // CASE 1: right child of N exists.
                if(N->right) {
                        tmp = N->right;
                        // find leftmost node.
                        while(tmp->left) {
                                tmp = tmp->left;
                        }
                // CASE 2: No right child.
                } else {
                        // keep climbing till you find a parent such that
                        // node is the left decedent of it.
                        while((tmp = N->parent)) {
                                if(tmp->left == N) {
                                        break;
                                }
                                N = tmp;
                        }
                }
                return tmp;
        }
        // No IOS.
        return NULL;
}

k //> given node
visitedK = false;
p = root;
do
{
	while( p!=NULL )
		stack.push(p);
		p = p->left;
	
	while( !stack.empty() ) // while - go to but the left node ladder
	{	
		temp = stack.pop()
		visit(temp);
		if( visitedK == true )
			return temp;
		if( temp == k )
			visitedK = true;
		if( temp->right )
			p = temp->right;
			break;
	}
}while( p!= NULL || !stack.empty() );

Assuming no parent pointers i.e. each node has just left and right pointers/children.

void findSuccessor(BinaryTree * root, BinaryTree * node, BinaryTree ** successor)
{
	if(root)
	{
		if(root->getLeft() == node)
		{
			*successor = root;
			return;
		}
		findSuccessor(root->getLeft(), node, successor);
		findSuccessor(root->getRight(), node, successor);
	}
}

BinaryTree * inorderSuccessor(BinaryTree * root, BinaryTree * node)
{
	BinaryTree * successor = root;

	if( !node )
	{
		return 0;
	}

	if( node->getRight() )
	{
		successor = node->getRight();
		while(successor->getLeft())
		{
			successor = successor->getLeft();
		}
	}
	else
	{
		findSuccessor(root, node, &successor);
	}

	return successor;
}

1. Check if the node is an internal node or external node.
2. if internal then return its right child's inorder traversals first node as succerssor node
3. else if external then check if it is the leftnode or right node ( p = parent(node) ,node =
left or right ? )
4. if leftnode then return parent(node) as successor
5. if rightnode then return parent(parent(node)) as the succesor

1. Check if the node is an internal node or external node.
2. if internal then return its right child's inorder traversals first node as succerssor node
3. else if external then check if it is the leftnode or right node ( p = parent(node) ,node =
left or right ? )
4. if leftnode then return parent(node) as successor
5. if rightnode then return parent(parent(node)) as the succesor