Next node of a node in Binary search tree To find the node next to a given node we need to consider two cases.
case 1: if the node has a right subtree then return the min node in its right subtree.
case 2: if the node doesn't have a right subtree then return the ancestor of the node whose left subtree contains the node.

class NodeWithParent {
    int data;
    NodeWithParent left;
    NodeWithParent right;
    NodeWithParent parent;

    NodeWithParent(int x) {
        data = x;
    }
}

public class nextNodeOfANodeInBST {

    public static NodeWithParent getMin(NodeWithParent root) {
        while (root.left != null) {
            root = root.left;
        }
        ;
        return root;
    }

    public static NodeWithParent nextNode(NodeWithParent curNode) {
        if (curNode == null) {
            return null;
        }
        if (curNode.right != null) {
            return getMin(curNode.right);
        } else if (curNode.data &gt; curNode.parent.data) // its the right child
        {
            // find an ancestor for which the curNode is in the left subtree
            while (curNode.parent != null &amp;&amp; curNode.data &gt; curNode.parent.data) {
                curNode = curNode.parent;
            }
            if (curNode.parent != null &amp;&amp; curNode.parent.data &lt; curNode.data)
                return curNode;
            else
                return curNode.parent;

        } else
            return curNode.parent;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        NodeWithParent root = new NodeWithParent(15);
        root.parent = null;
        root.left = new NodeWithParent(10);
        root.left.parent = root;
        root.right = new NodeWithParent(20);
        root.right.parent = root;
        root.left.left = new NodeWithParent(8);
        root.left.left.parent = root.left;
        root.right.right = new NodeWithParent(25);
        root.right.right.parent = root.right;
        root.right.left = new NodeWithParent(17);
        root.right.left.parent = root.right;
        root.left.right = new NodeWithParent(12);
        root.left.right.parent = root.left;
        root.left.left.left = new NodeWithParent(6);
        root.left.left.left.parent = root.left.left;
        root.left.right.left = new NodeWithParent(11);
        root.left.right.left.parent = root.left.right;
        root.right.left.left = new NodeWithParent(16);
        root.right.left.left.parent = root.right.left;
        root.right.right.right = new NodeWithParent(27);
        root.right.right.right.parent = root.right.right;
        NodeWithParent nextNode = nextNode(root.right.left);
        if (nextNode != null)
            System.out.println(nextNode.data);
        else
            System.out.println("No next node for " + root.right.left.data);
    }
}
1

NodeWithParent does not sound funky to me: why not try TreeNode.

2

You can drastically simplify (and rename) the nextNode method:

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

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

    TreeNode parent = node.parent;

    while (parent != null &amp;&amp; parent.right == node) {
        node = parent;
        parent = parent.parent;
    }

    return parent;
}


3

Also, it is conventional to start a class name with a capital letter (NextNodeOfANodeInBST). Actually, a better name for you class may be something as BSTUtils or, say, BinarySearchTreeUtils.

4

In your main you have root.parent = null; You don't have to: by default all reference fields in a class are initialized with null.

5

In case your class contains only static methods, it's customary to declare the constructor of such a class as private: it makes no sense to instantiate an object that does nothing in its own right.

Hope that helps.