127. Find the Inorder Successor of a Node in a BST

Given a binary search tree and a value that is guaranteed to exist in it, find its inorder successor - the next larger value in the tree. Print that value, or -1 if the given value is the maximum in the tree. The tree is given as space-separated level-order tokens, where 'N' means no node there: the first token is the root, then for each node dequeued in level order you read its left-child token then its right-child token (if input runs out early, remaining children are treated as N). The value is given on the next line.

Input: First line contains space-separated level-order tokens describing the BST ('N' marks an absent child). Second line contains the value to find the successor of. Output: Print the inorder successor's value, or -1 if the given value is the maximum in the tree.

1 <= number of nodes <= 10^5

This is the mirror image of 'inorder predecessor' - swapping every 'left' for 'right' (and vice versa) in the logic converts one into the other directly.

Given a value in a BST, find the next larger value that would come right after it in sorted order. Brute force: Perform a full inorder traversal, find the given value's position in the resulting sorted list, and return the next element - this works but does a full O(n) traversal when a more direct O(h) approach exists. Optimised: Exploiting the BST structure directly (checking for a right subtree, or tracking the last left-turn while walking from the root) finds the successor without ever needing a full traversal - bounded purely by the tree's height rather than its total size.

Do a complete inorder traversal of the BST, collecting every value into an array; since it's a BST, this array comes out sorted ascending for free. Then scan (or binary search) the array for the given value and return the very next element, or -1 if it was the last one. This is straightforward and correct, but it visits and stores every node in the tree even when the successor could be found much closer to the target. Time: O(n) Space: O(n)

Use Morris traversal to perform the inorder walk without recursion or an explicit stack: temporarily thread each node's inorder predecessor's right pointer to itself to simulate the traversal, then undo the threading as you pass back through. Stop as soon as the target value is visited and remember the very next value produced by the traversal as the successor. This still looks at nodes in the same sorted order as the brute approach, but drops the O(n) array (and the O(h) recursion stack) entirely, running in constant extra space. Time: O(n) Space: O(1)

Walk down from the root comparing the target value to each node: whenever the current node's value is greater than the target, it's a candidate successor, so remember it and move left (there may be something smaller-but-still-bigger further down); whenever it's less than or equal, move right instead. This single downward path finds the successor by exploiting BST ordering directly, without ever visiting the rest of the tree, so it only touches nodes on one root-to-target path instead of doing a full traversal. Time: O(h) Space: O(1)

1. If the node has a RIGHT subtree, its successor is simply the MINIMUM value in that right subtree (keep going left from the right child). 2. If it has no right subtree, walk down from the root toward this node, remembering the last node where you turned LEFT - that remembered node is the successor. 3. If you never turned left (the node is the maximum), there's no successor - print -1.

Time: O(h), where h is the tree's height. Space: O(1) if implemented iteratively.

Test with the given value being the tree's maximum (expect -1), a single-node tree, a value whose node has a right subtree (successor is that subtree's min), and a tree with 10^5 nodes for performance.

Be ready to explain the 'last left turn' rule clearly with a concrete example - it's the trickier of the two cases (versus the simple 'has right subtree' case) and interviewers often specifically probe understanding here.