Predecessor and Successor in BST

Medium
1972.

Predecessor and Successor in BST

Predecessor and Successor in BST is a medium coding problem on binary search and trees, asked in Amazon and Microsoft interviews.

You are given the root of a binary search tree with distinct values and an integer key (which may or may not be in the tree).

Return [pre, suc] where pre is the in-order predecessor of key — the largest value in the tree strictly less than key — and suc is its in-order successor — the smallest value strictly greater than key. Use -1 for whichever does not exist.

Example 1

Input
root = [50,30,70,20,40,60,80], key = 65
Output
[60,70]
Explanation
65 is not in the tree; the closest values around it are 60 and 70.

Example 2

Input
root = [8,1,9,null,4,null,10,3], key = 8
Output
[4,9]
Explanation
8 is in the tree. Its predecessor is the largest value below it (4) and its successor the smallest above it (9).

Example 3

Input
root = [10,2,11,1,5,null,null,null,null,3,6,null,4], key = 0
Output
[-1,1]
Explanation
Every value is above 0: no predecessor, and the successor is the minimum, 1.

Constraints

  • 1 <= number of nodes <= 10^5
  • 1 <= Node.val <= 10^6
  • all node values are distinct
  • 0 <= key <= 10^6
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} key
 * @return {number[]}
 */
var findPreSuc = function(root, key) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Predecessor and Successor in BST — Problem & Solution

Predecessor and Successor in BST solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Predecessor and Successor in BST is a medium coding problem on binary search and trees, asked in Amazon and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Binary Search, Trees
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given the root of a binary search tree with distinct values and an integer key (which may or may not be in the tree).

Return [pre, suc] where pre is the in-order predecessor of key — the largest value in the tree strictly less than key — and suc is its in-order successor — the smallest value strictly greater than key. Use -1 for whichever does not exist.

Example 1

Input: root = [50,30,70,20,40,60,80], key = 65
Output: [60,70]
Explanation: 65 is not in the tree; the closest values around it are 60 and 70.

Example 2

Input: root = [8,1,9,null,4,null,10,3], key = 8
Output: [4,9]
Explanation: 8 is in the tree. Its predecessor is the largest value below it (4) and its successor the smallest above it (9).

Example 3

Input: root = [10,2,11,1,5,null,null,null,null,3,6,null,4], key = 0
Output: [-1,1]
Explanation: Every value is above 0: no predecessor, and the successor is the minimum, 1.

Constraints

  • 1 <= number of nodes <= 10^5
  • 1 <= Node.val <= 10^6
  • all node values are distinct
  • 0 <= key <= 10^6

Hints for Predecessor and Successor in BST

  1. Hint 1

    The two answers are independent: one is the best value below key, the other the best above it.

  2. Hint 2

    For the predecessor, walk down from the root: a value below key is a candidate and anything better is in its right subtree; a value at or above key sends you left.

  3. Hint 3

    The successor is the mirror image. Each walk is O(height), and neither needs key to be in the tree.

How to solve Predecessor and Successor in BST

Two root-to-leaf walks: one that keeps the last value seen below key (the predecessor), one that keeps the last value seen above it (the successor). Equality simply counts as "not below" or "not above".

Approach

  1. Predecessor walk: start at the root with pre = -1. If the node's value is less than key, set pre to it and go right; otherwise go left.
  2. Successor walk: start at the root with suc = -1. If the node's value is greater than key, set suc to it and go left; otherwise go right.
  3. Return [pre, suc].

Why it works

In the predecessor walk, going right from a candidate discards only smaller values, and going left from a value at least key discards only values at least key, so the largest value below key is never discarded and is the last candidate recorded. The successor walk is symmetric.

Complexity

  • Time — O(h)
  • Space — O(1)

Pitfalls

  • When key is in the tree it is neither its own predecessor nor successor — the comparisons are strict.
  • Do not assume key is present; the walks never need to find it.

Reference solution

Python

from typing import List, Optional

def findPreSuc(root: Optional[TreeNode], key: int) -> List[int]:
    pre = -1
    node = root
    while node:
        if node.val < key:
            pre = node.val
            node = node.right
        else:
            node = node.left
    suc = -1
    node = root
    while node:
        if node.val > key:
            suc = node.val
            node = node.left
        else:
            node = node.right
    return [pre, suc]

Java

public static int[] findPreSuc(TreeNode root, int key) {
    int pre = -1, suc = -1;
    TreeNode node = root;
    while (node != null) {
        if (node.val < key) { pre = node.val; node = node.right; }
        else node = node.left;
    }
    node = root;
    while (node != null) {
        if (node.val > key) { suc = node.val; node = node.left; }
        else node = node.right;
    }
    return new int[] { pre, suc };
}

C++

vector<int> findPreSuc(TreeNode* root, int key) {
    int pre = -1, suc = -1;
    for (TreeNode* node = root; node; ) {
        if (node->val < key) { pre = node->val; node = node->right; }
        else node = node->left;
    }
    for (TreeNode* node = root; node; ) {
        if (node->val > key) { suc = node->val; node = node->left; }
        else node = node->right;
    }
    return {pre, suc};
}

JavaScript

var findPreSuc = function(root, key) {
    var pre = -1, suc = -1, node = root;
    while (node !== null) {
        if (node.val < key) { pre = node.val; node = node.right; }
        else node = node.left;
    }
    node = root;
    while (node !== null) {
        if (node.val > key) { suc = node.val; node = node.left; }
        else node = node.right;
    }
    return [pre, suc];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 189 binary search problems · the whole catalogue

Learn the technique: Binary Search · Binary Trees and Tree Traversals