Inorder Successor in Binary Tree | Algorithms

Inorder Successor in Binary Tree | Algorithms
Objec­tive: Given a Binary tree (Not binary Search Tree ), find the inorder suc­ces­sor of a node.
What is Inorder Suc­ces­sor: Inorder suc­ces­sor of a node is the next node in the inorder tra­ver­sal of the tree. For the last node in a tree, inorder suc­ces­sor will be NULL

Following is simple algorithm for finding Inorder Successor of binary tree.

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

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

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

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

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

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

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

Node *inorderSuccessorRec(Node *root, int key, Node *parent)

23

{

24	//Case 1: Current root itself is NULL, then successor is also NULL.

25	if (root==NULL)

26

return 0;

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

28	if (root->data == key)

29

{

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

31	if (root->right)

32	return findLeftMostNode(root->right);

33	//Case 2.2: Current root doesn't has right child, then parent of current root is successor.

34

else

35	return parent;

36

}

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

38

else

39

{

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

41	Node *left=inorderSuccessorRec(root->left,key,root);

42

if (left)

43	return left;

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

45	return inorderSuccessorRec(root->right,key,parent);

46

}

47

}

Case 1 : If the x has a right child then its inorder suc­ces­sor will the left most ele­ment in the right sub tree of x.

Case 3: if x is the right most node in the tree then its inorder suc­ces­sor will be NULL.

public class InOrderSuccessorBinaryTree {

    public static TreeNode n = null;

    public static Boolean nodeFound = false;

    public TreeNode inOrderSuccBiTree(TreeNode root, TreeNode x){

        nodeFound = false;

        if(x.right!=null){

            TreeNode temp = leftMostTreeNode(x.right);

            System.out.println("The In Order Successor for '" + x.data + "' is "+ temp.data );

            return temp;

        }

        return findRecur(root, x);

    }

 

    public TreeNode findRecur(TreeNode root, TreeNode x){

        if(root==null) return null;

        if(root==x||(n = findRecur(root.left,x))!=null||(n=findRecur(root.right,x))!=null){

 

            if(n!=null){

                if(root.left==n){

                    nodeFound = true;

                    System.out.println("The In Order Successor for '" + x.data + "' is "+ root.data );

                    return null;

                }

            }

            return root;

        }

        return null;

    }

    public TreeNode leftMostTreeNode(TreeNode x){

        while(x.left!=null){

            x = x.left;

        }

        nodeFound = true;

        return x;

    }

}

https://rajneesh2k10.wordpress.com/2011/06/25/inorder-successor/

Node *findRightSuccessor(Node *root)

{

    while (root->left)

        root=root->left;

    return root;

}

Node *inorderSuccessor(Node *root, int key, Node *parent)

{

    if (root==NULL)

        return 0;

    if (root->data == key)

    {

        if (root->right)

            return findRightSuccessor(root->right);

        else

            return parent;

    }

    Node *left=inorderSuccessor(root->left,key,root);

    if (left)

        return left;

    return inorderSuccessor(root->right,key,parent);

}

Node *inorderSuccessor(Node *root, int key)

{

    return inorderSuccessor(root,key,NULL);

}

Read full article from Inorder Successor in Binary Tree | Algorithms