up vote 1 down vote favorite
1

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 > curNode.parent.data) // its the right child
        {
            // find an ancestor for which the curNode is in the left subtree
            while (curNode.parent != null && curNode.data > curNode.parent.data) {
                curNode = curNode.parent;
            }
            if (curNode.parent != null && curNode.parent.data < 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);
    }
}
share|improve this question
up vote 1 down vote

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 && 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.

share|improve this answer
up vote 0 down vote 
        // TODO Auto-generated method stub

This is a red flag that this code isn't yet ready for other people to review, because you don't seem to have reviewed it yourself.

It's not quite the only comment, but there are only two more. The node class really needs explicit documentation of the invariants which are assumed to hold, because otherwise there's no way of checking whether the methods which modify it maintain / restore those invariants. For this reason also I would say that the code isn't yet ready for review.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.