Revision history [back]

Sure, here's an implementation of a getNextItem function for a Java binary search tree:

public TreeNode getNextItem(TreeNode root, int key) {
    // Find the node with the given key
    TreeNode curr = root;
    while (curr != null && curr.data != key) {
        if (key < curr.data) {
            curr = curr.left;
        } else {
            curr = curr.right;
        }
    }

    if (curr == null) {
        return null;
    }

    // If the node has a right subtree, return the minimum value in that subtree
    if (curr.right != null) {
        curr = curr.right;
        while (curr.left != null) {
            curr = curr.left;
        }
        return curr;
    }

    // If the node does not have a right subtree, find the nearest ancestor
    // whose left child is also an ancestor and return that node
    TreeNode ancestor = root;
    TreeNode successor = null;
    while (ancestor != curr) {
        if (curr.data < ancestor.data) {
            successor = ancestor;
            ancestor = ancestor.left;
        } else {
            ancestor = ancestor.right;
        }
    }
    return successor;
}

This function takes the root node of the binary search tree and a key as input, and returns the node with the smallest key greater than the input key.

The function first finds the node with the input key using a standard binary search algorithm. If the node has a right subtree, the function returns the minimum value in that subtree. Otherwise, the function traverses up the tree to find the nearest ancestor whose left child is also an ancestor. This node is the next highest element in the binary search tree.