429. Populate the Inorder Successor of Every Node in a BST

Given a binary search tree, find every node's inorder successor (the next larger value in the tree, or -1 for the node with the maximum value). Print one 'value:successor' pair per node, in inorder order, space-separated on a single line.

Input: A single line of space-separated level-order tokens ('N' for missing children) describing the BST. Output: Print one 'value:successor' pair per node in inorder order, space-separated on a single line, using -1 for the node holding the maximum value.

1 <= number of nodes <= 10^5

This is a great example of 'batch the computation' thinking - when you need the SAME kind of answer for every node, look for a single traversal that naturally produces all of them together, rather than repeating a per-node algorithm n times.

Find and record the inorder successor (next larger value) for EVERY node in a BST at once, not just one at a time. Brute force: For every node individually, run the standalone 'find inorder successor' algorithm (checking for a right subtree, or tracking the last left-turn from the root) - this costs O(n * h) total, since each individual lookup costs O(h) and there are n nodes to look up. Optimised: Since inorder traversal already visits every node in exactly sorted order, a SINGLE pass that simply remembers 'the previously visited node' and pairs it with the CURRENT node as its successor computes every single node's successor simultaneously - reducing n separate O(h) lookups down to one single O(n) traversal.

Traverse the tree in reverse inorder (right subtree, then node, then left subtree), which visits nodes in strictly decreasing order, while carrying a single running variable that holds the value of the previously visited node (initialized to -1). At each node, first assign its successor to whatever the running variable currently holds, then update the running variable to the current node's value before recursing into the left subtree. This works because when descending in decreasing order, the node you visited most recently is always exactly the next larger value for the node you are about to visit, so successors are assigned correctly in a single pass without any extra array to store the whole traversal, only the O(h) recursion stack is needed. Time: O(n) Space: O(h)

Perform one standard inorder traversal (left, node, right) of the BST, which visits every node in strictly increasing order of value, and store the visited nodes in a list. Once the list is built, each node's successor is simply the node immediately after it in that list, with the last node's successor set to -1. This works because inorder traversal of a BST always produces sorted order, so a single O(n) traversal followed by a linear scan of the stored list assigns every successor correctly, avoiding the repeated re-scanning of the brute-force approach. Time: O(n) Space: O(n)

For every node in the BST, independently search the entire tree for the node with the smallest value that is still strictly greater than the current node's value, and record that as its inorder successor (or -1 if none exists). This works because it directly checks the definition of an inorder successor - the smallest value greater than the current one - but it repeats a full tree scan for every single node, making it very wasteful since the same comparisons get redone over and over. Time: O(n^2) Space: O(h)

1. Perform a single inorder traversal - this naturally visits every node in ascending order. 2. Pair each visited value with the value visited IMMEDIATELY AFTER it in this same traversal - that's its successor. 3. The very last value visited pairs with -1 (it has no successor, being the maximum).

Time: O(n) - one single inorder traversal handles every node's successor at once. Space: O(h) for the recursion stack, plus O(n) for storing all the resulting pairs.

Test a single-node tree (its only pair is 'value:-1'), and n=10^5 nodes for performance since the entire answer comes from one inorder pass.

Be ready to contrast this 'populate ALL successors at once' problem with the standalone 'find ONE node's successor' problem - recognizing that batching the computation via a single traversal is dramatically more efficient than repeating the single-node algorithm n times.