Code Logo

BST Inorder Successor

Published at25 Jul 2026
Created by
Binary Search Tree Easy 4 views
Like0

Given an array representing a Binary Search Tree (BST) in level-order and a target value, find the in-order successor of the target. The in-order successor is the smallest value in the BST that is greater than the target.

For example, in the BST [5, 3, 8, 1, 4, 7, 9], the successor of 4 is 5. The successor of 5 is 7. If the target is the largest value in the tree (like 9), it has no successor — return 0. If the target does not exist in the tree, also return 0.

The in-order successor is a key concept in BST operations. It is used in deletion (replacing a node with its successor), finding the next element in sorted order, and implementing ceiling queries. The successor is found by traversing the tree: if the target is smaller than the current node, the current node is a candidate and we move left; otherwise, we move right without updating the candidate.

The algorithm maintains a candidate variable initialized to 0. Start at the root. If the current node's value is greater than the target, it is a potential successor — update the candidate and move left. If it is less than or equal to the target, move right (the successor must be larger). Continue until the index goes out of bounds, then return the candidate.

Edge cases include an empty tree (return 0), a target larger than every node (return 0), a target equal to a node that has a right subtree (the successor is the minimum value in that right subtree), and the target being the minimum value in the tree (the successor is the next larger value).

Example Input & Output

Example 1
Input
[10,20,30],10
Output
20
Explanation

Next after 10 is 20

Example 2
Input
[5,10,15,20],15
Output
20
Explanation

Next after 15 is 20

Example 3
Input
[1],1
Output
-1
Explanation

Single node, no successor

Example 4
Input
[1,2,3,4,5],3
Output
4
Explanation

Next after 3 is 4

Example 5
Input
[1,2,3,4,5],5
Output
-1
Explanation

5 is max, no successor

Algorithm Flow

Recommendation Algorithm Flow for BST Inorder Successor

Solution Approach

Traverse the BST, tracking the last node that is greater than the target as a potential successor.

function inorderSuccessor(arr, target)
  succ = 0, i = 0
  while i < length(arr)
    if arr[i] > target
      succ = arr[i]
      i = 2 * i + 1
    else
      i = 2 * i + 2
  return succ

Initialize succ to 0 and i to 0 (root). While i is within bounds: if the current node is greater than the target, it is a candidate for successor — update succ and move left (looking for a smaller value that is still greater than target). If the current node is less than or equal to target, move right (the successor must be larger). After traversing all possible paths, return succ.

Time complexity is O(log n) for balanced trees, O(n) worst case. Space complexity is O(1).

Best Answers

java
class Solution {
    public int solution(int[] nums, int t) {
        for(int i=0;i<nums.length;i++){if(nums[i]==t&&i<nums.length-1)return nums[i+1];}
        return -1;
    }
}