Inorder Successor in BST

Medium
1971.

Inorder Successor in BST

Inorder Successor in BST is a medium coding problem on depth-first search, binary search and trees, asked in Amazon and Microsoft interviews.

You are given the root of a binary search tree with distinct values and a value x that occurs in the tree.

Return the value of the in-order successor of the node holding x — the node that comes right after it in an in-order traversal, i.e. the smallest value greater than x. If x is the largest value in the tree, return -1.

Example 1

Input
root = [2,1,3], x = 2
Output
3
Explanation
In increasing order the values are 1, 2, 3; the one after 2 is 3.

Example 2

Input
root = [20,8,22,4,12,null,null,null,null,10,14], x = 14
Output
20
Explanation
14 has no right subtree; its successor is the nearest ancestor it lies to the left of — 20.

Example 3

Input
root = [20,8,22,4,12,null,null,null,null,10,14], x = 22
Output
-1
Explanation
22 is the largest value, so it has no successor.

Constraints

  • 1 <= number of nodes <= 10^5
  • 1 <= Node.val <= 10^5
  • all node values are distinct
  • x is the value of a node in the tree

Follow-up: Can you find it in O(height) time?

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} x
 * @return {number}
 */
var inorderSuccessor = function(root, x) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Inorder Successor in BST — Solution in Python, Java & C++

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

Inorder Successor in BST is a medium coding problem on depth-first search, binary search and trees, asked in Amazon and Microsoft interviews.

Problem statement

You are given the root of a binary search tree with distinct values and a value x that occurs in the tree.

Return the value of the in-order successor of the node holding x — the node that comes right after it in an in-order traversal, i.e. the smallest value greater than x. If x is the largest value in the tree, return -1.

Example 1

Input: root = [2,1,3], x = 2
Output: 3
Explanation: In increasing order the values are 1, 2, 3; the one after 2 is 3.

Example 2

Input: root = [20,8,22,4,12,null,null,null,null,10,14], x = 14
Output: 20
Explanation: 14 has no right subtree; its successor is the nearest ancestor it lies to the left of — 20.

Example 3

Input: root = [20,8,22,4,12,null,null,null,null,10,14], x = 22
Output: -1
Explanation: 22 is the largest value, so it has no successor.

Constraints

  • 1 <= number of nodes <= 10^5
  • 1 <= Node.val <= 10^5
  • all node values are distinct
  • x is the value of a node in the tree

Follow-up: Can you find it in O(height) time?

Hints for Inorder Successor in BST

  1. Hint 1

    The successor is the smallest value larger than x, so you never need the full traversal.

  2. Hint 2

    If the node of x has a right subtree, the successor is that subtree's leftmost node. Otherwise it is an ancestor.

  3. Hint 3

    Both cases are covered by one walk from the root: at a node larger than x, remember it and go left; otherwise go right. The last remembered node is the answer.

How to solve Inorder Successor in BST

Search for x from the root, and every time the walk goes left from a value larger than x, record that value: the last one recorded is the smallest value larger than x.

Approach

  1. Set succ = -1 and start at the root.
  2. If the node's value is greater than x, set succ to it and move left (a smaller candidate may be there).
  3. Otherwise move right (everything at or below this node's left is not larger than x).
  4. When the walk ends, return succ.

Why it works

Moving left from a candidate discards only values larger than that candidate; moving right from a value at most x discards only values at most x. The smallest value above x is therefore never discarded, and the walk reaches it — either as the last ancestor turned left at, or as the leftmost node of x's right subtree.

Complexity

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

Pitfalls

  • Stopping when x is found loses the right-subtree case: keep walking right from x.
  • The successor of the maximum does not exist — return -1, not x.

Reference solution

Python

from typing import Optional

def inorderSuccessor(root: Optional[TreeNode], x: int) -> int:
    succ = -1
    node = root
    while node:
        if node.val > x:
            succ = node.val
            node = node.left
        else:
            node = node.right
    return succ

Java

public static int inorderSuccessor(TreeNode root, int x) {
    int succ = -1;
    TreeNode node = root;
    while (node != null) {
        if (node.val > x) { succ = node.val; node = node.left; }
        else node = node.right;
    }
    return succ;
}

C++

int inorderSuccessor(TreeNode* root, int x) {
    int succ = -1;
    TreeNode* node = root;
    while (node) {
        if (node->val > x) { succ = node->val; node = node->left; }
        else node = node->right;
    }
    return succ;
}

JavaScript

var inorderSuccessor = function(root, x) {
    var succ = -1, node = root;
    while (node !== null) {
        if (node.val > x) { succ = node.val; node = node.left; }
        else node = node.right;
    }
    return succ;
};

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

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Search