Finding Inorder Successor in Binary Search Tree [duplicate]

Question

This question already has answers here:

In Order Successor in Binary Search Tree (19 answers)

Closed 5 years ago.

I'm creating Binary Search Tree class I got all my functions working accept the Successor.

My tree input is 30 10 45 38 20 50 25 33 8 12

When I print Inorder traversal it come up as

8 10 12 20 25 30 33 38 45 50

When I enter value 8 its says its successor is 12. Same for input 10 and 12 itself.

When I enter value 33 it says successor is 50. Which its not.

I can't seem to fix it. Any help of suggestion will be appreciated.

I'm calling it in main like:

BinarySearchTree BST = new BinarySearchTree(array);

BST.getSeccessor(a); // where a is user input to find it successor

Following is my code...

 public TreeNode Successor(TreeNode node) {
        if (node == null) 
         return node; 
        if (node.right != null) {
            return leftMostNode(node.right);
        }
        TreeNode y = node.parent;
        while (null != y && (y.right).equals(node)) {
            node = y;
            y = y.parent;
        }
      return y;
    }

    public static TreeNode leftMostNode(TreeNode node) {
     if (null == node) { return null; }

     while (null != node.left) {
      node = node.left;
     }
     return node;
    }

    /** Search value in Tree need for Successor **/
    public TreeNode Search(int key) {
        TreeNode node = root;                           
        while (node != null) {
            if (key < node.value) {                     
                node = node.left;
            } else if (key  > node.value) {             
                node = node.right;
            } 
            return node;
        }
        return null;
    }

    /** Returns Successor of given value **/
    public int getSuccessor(int val) {
        TreeNode node = Successor(Search(val));
        return node.value; 
    }

Answer 1

I added working solution based on pseudo-code in Niklas answer :

public TreeNode successor(TreeNode node) {
    if (node == null)
        return node;

    if (node.right != null) {
        return leftMostNode(node.right);
    }

    while (null != node.parent /*while we are not root*/ 
            && node.parent.right == node) /* and while we are "right" node */ {

        node = node.parent; // go one level up
    }

    return node.parent;
}

For this to work, you have to fix implementation of some of your methods (provided below) :

/** Search value in Tree need for Successor **/
public TreeNode search(int key) {
    TreeNode node = root;
    while (node != null 
            && key != node.value) {

        if(key < node.value) {
            node = node.left;
        } else if (key > node.value) {
            node = node.right;
        }
    }
    return node;
}

/** Returns Successor of given value **/
public int getSuccessor(int val) {
    TreeNode node; 
    if (null == (node = search(val))
            || (null == (node = successor(node))) {
        // either val is not in BST, or it is the last value-> no successor
        return ERROR_CODE; // -1, for instance;
    }

    return node.value;
}

Answer 2

A possible algorithm would be the following:

1. If you have a non-empty right subtree, the successor is the smallest value in that subtree
2. Otherwise, walk up the tree unless you are no longer the right child of your parent or until you reach the root
3. If you are at the root now, you have no successor. Otherwise, walk up one more step and you are at the successor

Example:

if node.right != null
    return leftmostInSubtree(node.right)
while node != root && node.parent.right == node
    node = node.parent
if node == root
    return null
return node.parent

Answer 3

The inorder successor is going to be

if (node.hasRight())
    node = node.getRight();
else {
    while (node.isRightChild())
        node = node.getParent();
    return node.getParent();
}
while (node.hasLeft())
    node = node.getLeft();
return node;

Might be a good idea to put some null checks in there, too.

Answer 4

I think the above code won't work for the rightmost last node. Here is the improved version:

if(node.right!=null)
{
node=node.right;
while(node.left!=null)
node=node.left;
}`

else if(node.parent==root)
return null;
else if(node==node.parent.left)
node=node.parent;
else
{
while(node.parent!=null)
node=node.parent
}

return node;