Algo#1: Inorder Predecessor in Binary Tree

Algo#1: Inorder Predecessor in Binary Tree

Step 1: Current root itself is NULL, then predecessor is also NULL.

Step 2: Current root contains value same as key for which we are looking predecessor.

        2.1: Current root has left child, then right most node of left child is predecessor.

        2.2: Current root doesn't has left child, then parent of current root is predecessor.

Step 3: Current root is not the target node for which we are looking predecessor.

        3.1: Search target node and its predecessor in left side of tree recursively, and return if found.

        3.2: Search target node and its predecessor in right side of tree recursively, and return.

Node *findRightMostNode(Node *root)

017

{

018	while (root->right)

019	root=root->right;

020	return root;

021

}

022

023	Node *inorderPredecessorRec(Node *root, int key, Node *parent)

024

{

025	//Case 1: Current root  itself is NULL, then predecessor is also NULL.

026	if (root==NULL)

027

return 0;

028	//Case 2: Current root  contains value same as key for which we are looking predecessor.

029	if (root->data == key)

030

{

031	//Case 2.1: Current root has left child, then right most node of left child is predecessor.

032	if (root->left)

033	return findRightMostNode(root->left);

034	//Case 2.2: Current root  doesn't has left child, then parent of current root is predecessor.

035

else

036	return parent;

037

}

038	//Case 3: Current root  is not the target node for which we are looking predecessor.

039

else

040

{

041	//Case 3.1: Search target node and its predecessor in left side of tree recursively, and return if found.

042	Node *left=inorderPredecessorRec(root->left,key,parent);

043

if (left)

044	return left;

045	//Case 3.2: Search target node and its predecessor in right side of tree recursively, and return.

046	return inorderPredecessorRec(root->right,key,root);

047

}

048

}

Algo#2: Inorder Successor in Binary Tree
Also http://massivealgorithms.blogspot.com/2015/09/inorder-predecessor-and-successor-for.html

Algo#3: Postorder Predecessor in Binary Tree

Step 1: If current root is NULL, then pred(current root) is NULL.

Step 2: If current root is target node for which we are looking for predecessor.

        2.1: If current root has a right child, r, then pred(current root) is r.

        2.2: Otherwise If current root has a left child, l, then pred(current root) is l.

        2.3: Otherwise if current root has a left sibling, ls, then pred(current root) is ls

      2.4: Otherwise if current root has an ancestor, v, which is a right child and has a left sibling, vls, then pred(current root) is vls

        2.5: Otherwise, pred(current root) is undefined.

Step 3: Current root is not the target node for which we are looking predecessor.

        3.1: Search target node and its predecessor in left side of tree recursively, and return if found.

        3.2: Search target node and its predecessor in right side of tree recursively, and return.

Node *postorderPredecessorRec(Node *root, int key,Node *direct_parent, Node *parent,Node * ance_leftsib)

019

{

020	//Case 1: If current root is NULL, then pred(current root) is NULL.

021	if (root==NULL)

022

return 0;

023	//Case 2: If current root is target node for which we are looking for predecessor.

024	if (root->data == key)

025

{

026	//Case 2.1: If current root has a right child, r, then pred(current root) is r.

027	if(root->right)

028	return root->right;

029	//Case 2.2: Otherwise If current root has a left child, l, then pred(current root) is l.

030	if(root->left)

031	return root->left;

032	//Case 2.3: Otherwise if current root has a left sibling, ls, then pred(current root) is ls

033	else if(direct_parent != NULL && direct_parent->left!=NULL && direct_parent->left!=root )

034	return direct_parent->left;

035	//Case 2.4: Otherwise if current root has an ancestor, v, which is a right child and has a left sibling, vls, then pred(current root) is vls

036	else if(parent != NULL && parent->left==ance_leftsib && ance_leftsib!=NULL)

037	return ance_leftsib;

038	//Case 2.5: Otherwise, pred(current root) is undefined.

039

else

040	return NULL;

041

}

042	//Case 3: Current root is not the target node for which we are looking predecessor.

043

else

044

{

045	//Case 3.1: Search target node and its predecessor in left side of tree recursively, and return if found.

046	Node *left=postorderPredecessorRec(root->left,key,root,parent,ance_leftsib);

047

if (left)

048	return left;

049	//Case 3.2: Search target node and its predecessor in right side of tree recursively, and return.

050

//TRICK:

051	if(root->left)

052	return postorderPredecessorRec(root->right,key,root,root,root->left);

053

else

054	return postorderPredecessorRec(root->right,key,root,parent,ance_leftsib);

055

}

056

}

Algo#4: Postorder Successor in Binary Tree

Step 1: If current root is NULL, then succ(current root) is NULL.

Step 2: If current root is target node for which we are looking for successor.

        2.1: If current root is the root of the tree, succ(current root) is undefined.

        2.2: Otherwise, if current root is a right child, succ(current root) is parent(current root).

        2.3: Otherwise current root is a left child and the following applies:

           2.3.1: If u has a right sibling, r, succ(current root) is the leftmost leaf in r's sub-tree

           2.3.2: Otherwise succ(current root) is parent(current root).
           2.3.3: If none of above applies, then succ(current root) doesn't exist.

Step 3: Current root is not the target node for which we are looking predecessor.

        3.1: Search target node and its predecessor in left side of tree recursively, and return if found.

        3.2: Search target node and its predecessor in right side of tree recursively, and return.

015	Node *leftmostLEAFnotNODE(Node *root)

016

{

017	while (root->left || root->right)

018

{

019	if(root->left) root=root->left;

020	else root=root->right;

021

}

022

023	return root;

024

}

025

026	Node *postorderSuccessorRec(Node *root, int key,Node *direct_parent, Node *parent,Node * treeroot)

027

{

028	//Case 1: If current root is NULL, then succ(current root) is NULL.

029	if (root==NULL)

030

return 0;

031	//Case 2: If current root is target node for which we are looking for successor.

032	if (root->data == key)

033

{

034	//Case 2.1: If current root is the root of the tree, succ(current root) is undefined.

035	if(root == treeroot)

036	return NULL;

037	//Case 2.2: Otherwise, if current root is a right child, succ(current root) is parent(current root).

038	else if(direct_parent != NULL && direct_parent->right==root)

039	return direct_parent;

040	//Case 2.3: Otherwise current root is a left child and the following applies:

041

042	//Case 2.3.1: If u has a right sibling, r, succ(current root) is the leftmost leaf in r's sub-tree

043	else if(direct_parent != NULL && direct_parent->left==root && direct_parent->right!=NULL)

044	return leftmostLEAFnotNODE(direct_parent->right);

045	//Case 2.3.2: Otherwise succ(current root) is parent(current root).

046	else if(direct_parent != NULL && direct_parent->left==root && direct_parent->right==NULL)

047	return direct_parent;

048	//Case 2.3.3: If none of above applies, then succ(current root) doesn't exist.

049

else

050	return NULL;

051

}

052	//Case 3: Current root is not the target node for which we are looking successor.

053

else

054

{

055	//Case 3.1: Search target node and its successor in left side of tree recursively, and return if found.

056	Node *left=postorderSuccessorRec(root->left,key,root,root,treeroot);

057

if (left)

058	return left;

059	//Case 3.2: Search target node and its successor in right side of tree recursively, and return.

060	return postorderSuccessorRec(root->right,key,root,parent,treeroot);

061

}

062

}

063

064	Node *postorderSuccessor(Node *root, int key)

065

{

066	return postorderSuccessorRec(root,key,NULL,NULL,root);

067

}