Saturday, December 12, 2015

get InOrder sucessor of a given node in a BST

    private Stack<BinarySearchTree> S;
    public int inOrderSuccessor(int data)    {
        S = new Stack<
BinarySearchTree>();
       
BinarySearchTree Current = getNode(this, data);
        if(Current.right!=null)    {
            return getMin(Current.right).data;
        }    else    {
           
BinarySearchTree parent = S.pop();
            if(parent.left==Current)
                return parent.data;
            else
                return S.pop().data;
        }
    }
    private
BinarySearchTree getMin(BinarySearchTree T)    {
        while(T.left!=null)
            T=T.left;
        return T;
    }
    private
BinarySearchTree getNode(BinarySearchTree T, int data)    {
        if(T==null)    return null;
        else if(data==T.data)        {
            return T;
        }
        else if(data<T.data) {
            S.add(T);
            return getNode(T.left, data);
        }
        else {
            S.add(T);
            return getNode(T.right, data);
        }
    }
UA-39217154-2