Predecessor and Successor in BST

Given the root of a binary search tree and a key, return the inorder predecessor and inorder successor of that key. Pattern focus: LCA in BST. The search path and inorder ordering help you identify the nearest smaller and larger values around the key.

Input Format

root = binary tree root, key = target value

Output Format

[predecessor, successor] with -1 used when absent

Constraints

  • 1 <= number of nodes <= 10^5
  • -10^9 <= node values <= 10^9
  • root and key must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

root = [8,4,12,2,6,10,14]
key = 10

Output:

[8,12]

Explanation:

The predecessor of 10 is 8 and the successor is 12.

Example 2:

Input:

root = [8,4,12,2,6,10,14]
key = 5

Output:

[4,6]

Explanation:

5 is not in the tree, but the nearest smaller and larger values are still 4 and 6.

Loading...
Predecessor and Successor in BST