// Given a value in a binary search tree, write an algorithm that returns the next greatest value. // The tree is assumed to contain the given value. // returns val if no greater val exists public static int nextGreaterVal(Node root, int val) { int closestParentVal = val; Node curr = root; while (curr != null) { if (curr.val == val) { // if a right node exists it must be // the closest value greater than val // because it's greater than val and smaller // than any greater parent node. if (curr.right != null) return curr.right.val; return closestParentVal; } else if (val curr.val) */ { curr = curr.right; } } return val; }

First successful solution involved storing the traversal path in a stack. The interviewer then asked me to do it with constant memory, which I wasn't able.

Find a number in the bst that is second greatest than the given value, so given value x) if (tree.left == null) return tree.head find(tree.left, x) if (tree.head x) if (tree.left === null) return tree.head find(tree.left, x) if (tree.head < x) if (tree.right === null) return tree.parent find(tree.right, x) if (tree.head === x) if (tree.right === null) return tree.head

1) Check and return right child if exist 2) Check if current node is a left node, if yes, return parent. 3) If not, current element is biggest in current subtree, return parent of parent as that is the next biggest element.