Binary Search Tree doesn't return correct inorder successor

Question

I am trying to solve the following question from geeksforgeeks.com http://www.geeksforgeeks.org/inorder-predecessor-successor-given-key-bst/ using Java. I am getting correct successor while searching for the keys that are already in the tree, however for values not in the tree I am unable to get correct successor for the key.Can someone advise where I am going wrong.

package com.geeksforgeeks.binarysearchtree;

public class BinarySearchTree {
public Node root;
static class Node
{
    int data;
    Node right;
    Node left;

    public Node(int data)
    {
        this.data=data;
        this.right=null;
        this.left=null;
    }
}

public void insert(int data)
{   
    root=treeInsert(root,data);     
}

public Node treeInsert(Node root,int data)
{
    if(root==null)
        {
        root=new Node(data);            
        return root;
        }

    if(data >= root.data)
        root.right= treeInsert(root.right,data);
    else 
        root.left= treeInsert(root.left,data);

    return root;
}

public void delete(int data)
{       
    root=recDelete(root,data);
}

public Node recDelete(Node root,int data)
{
    //Base Case
    if(root==null)return root;

    //Recurring down the tree
    if(root.data>data)
        root.left=recDelete(root.left,data);
    else if(root.data<data)
        root.right=recDelete(root.right,data);

    else
    {           
        if(root.left==null)return root.right;
        else if(root.right==null)return root.left;          

        root.data= min(root.right);         
        root.right=recDelete(root.right,root.data);     
    }

    return root;
}
private int min(Node root) {
    // TODO Auto-generated method stub
    int minv=root.data;

    while(root.left!=null)
    {
        minv=root.left.data;
        root=root.left;
    }

    return minv;
}

public static void main(String[] args) {
    // TODO Auto-generated method stub

    BinarySearchTree tree = new BinarySearchTree();

    /* Let us create following BST
          50
       /     \
      30      70
     /  \    /  \
   20   40  60   80 */
    tree.insert(50);
    tree.insert(30);
    tree.insert(20);
    tree.insert(40);
    tree.insert(70);
    tree.insert(60);
    tree.insert(80);
    System.out.println("successor :"+tree.inOrderSuccessor(50));        

    tree.delete(20);
    tree.inOrder();

    tree.delete(30);
    tree.inOrder();        

    tree.delete(50);
    tree.inOrder();
}

private int inOrderSuccessor(int i) {

    Node successor=recursiveInOrderSuccessor(root,i);
    if(successor!=null)
    return successor.data;
    else
        return -1;      
}

private Node recursiveInOrderSuccessor(Node root2,int i) {

    Node successor=null;
    //if tree is empty

    if(root2==null)return null;

    //if root is the key
    if(root2.data==i)
    {
        successor=root2.right;
        if(root2.right!=null)
        {               
            while(successor.left!=null)
                successor=successor.left;
        }

        return successor;
    }

    Node newSuccessor = null;
    if(root2.data>i)
    {
        successor=root2;
        newSuccessor=recursiveInOrderSuccessor(root2.left,i);
    }
    else
    {
        successor=root2;
        newSuccessor=recursiveInOrderSuccessor(root2.right,i);
    }

    if(newSuccessor==null)
    return successor;
    else
        return newSuccessor;        
}

private void inOrder() {
    // TODO Auto-generated method stub      
    inOrderRecursion(root);
}

private void inOrderRecursion(Node root) {
    // TODO Auto-generated method stub
    if(root!=null)
    {
        inOrderRecursion(root.left);
        System.out.println(root.data);
        inOrderRecursion(root.right);
    }       
}
}

Answer 1

You need to make change in recursiveInOrderSuccessor().

• Capture the successor only when value of the current node being traversed is greater, i.e. you shouldn't be capturing a node as successor in case of (root2.data < i).
• Return null if you reach null and don't find any greater value.

Given below is the changed code. Find Demo here

    private Node recursiveInOrderSuccessor(Node root2,int i) {
        if(root2 == null) return null;
        Node successor = null, succ2 = null;
        if(root2.data == i) {
            successor = root2.right;
            while(successor.left != null){
                successor = successor.left;
            }
            return successor;
        }

        if(root2.data > i){
            successor = root2;
            succ2 = recursiveInOrderSuccessor(root2.left, i);
            if(succ2 != null && succ2.data < successor.data)
                return succ2;
            else
                return successor;
        }
        else{
            return recursiveInOrderSuccessor(root2.right, i);
        }
    }