428. Find the Inorder Predecessor of a Node in a BST

Given a binary search tree and a value that is guaranteed to exist in it, find its inorder predecessor - the next smaller value in the tree. Print that value, or -1 if the given value is the minimum 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 predecessor of. Output: Print the inorder predecessor's value, or -1 if the given value is the minimum in the tree.

1 <= number of nodes <= 10^5

Mastering BOTH predecessor and successor together builds the foundation for BST-based order-statistics operations (like finding ranks, ranges, or nearby values) used throughout more advanced tree problems.

Given a value in a BST, find the next smaller value that would come right before it in sorted order. Brute force: Perform a full inorder traversal, find the given value's position, and return the previous element - correct, but a full O(n) traversal is more than necessary. Optimised: Directly exploiting BST structure (checking for a left subtree, or tracking the last right-turn while descending from the root) finds the predecessor in time bounded by the tree's height alone.

Perform a full inorder traversal of the BST to collect all values into a sorted array (inorder traversal of a BST always yields sorted order). Then scan the array linearly to find the index of the target value, and the predecessor is the element right before it (or -1 if it's the first element). This is easy to reason about but does more work than necessary in the search step once the sorted array already exists. Time: O(n) Space: O(n)

Build the same sorted array via an inorder traversal, but since the array is guaranteed sorted, locate the target value's index with binary search instead of a linear scan. The traversal itself still costs O(n), but the search step drops from O(n) to O(log n), which matters when the predecessor of many different values needs to be looked up against the same collected array. Time: O(n) Space: O(n)

Skip building any array at all. Walk from the root, keeping a 'best candidate' variable initialized to none: at each node, if the node's value is less than the target, it's a valid predecessor candidate, so remember it and move right (looking for something even closer); if the node's value is greater than or equal to the target, move left without updating the candidate. When you fall off the tree, the remembered candidate is the answer (or -1 if none was ever set). This uses the BST ordering directly, needs only O(h) steps and O(1) extra space, and never touches nodes outside the search path. Time: O(h) Space: O(1)

1. If the node has a LEFT subtree, its predecessor is the MAXIMUM value in that left subtree (keep going right from the left child). 2. If it has no left subtree, walk down from the root toward this node, remembering the last node where you turned RIGHT - that remembered node is the predecessor. 3. If you never turned right (the node is the minimum), there's no predecessor - 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 minimum (expect -1), a single-node tree, a value whose node has a left subtree (predecessor is that subtree's max), and a tree with 10^5 nodes for performance.

This problem and inorder successor are almost always asked together or as immediate follow-ups to each other - be ready to implement both back-to-back, noting they're exact mirror images.