Code Logo

BST Inorder Predecessor

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

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

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

The in-order predecessor is an important concept in BST operations. It is used in deletion (replacing a node with its predecessor), finding the previous element in sorted order, and implementing floor queries. The predecessor is found by traversing the tree: if the target is larger than the current node, move right and update the candidate; otherwise, move left.

For the array-based representation, start at index 0. Maintain a candidate variable for the predecessor (initialized to 0). If the current node is less than the target, update the candidate and move right (2i+2). If greater, move left (2i+1). Continue until the index goes out of bounds.

Edge cases include an empty tree (return 0), a target smaller than every node (return 0), and a target equal to a node that has a left subtree (the predecessor is the maximum value in that left subtree).

Example Input & Output

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

Predecessor of 40 is 30

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

Min has no predecessor

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

1 is minimum, no predecessor

Example 4
Input
[5,10,15],10
Output
5
Explanation

Predecessor of 10 is 5

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

Predecessor of 3 is 2

Algorithm Flow

Recommendation Algorithm Flow for BST Inorder Predecessor

Solution Approach

Traverse the BST, tracking the last node that is smaller than the target.

function solution(arr, target) {
  var pred = 0, i = 0;
  while (i < arr.length) {
    if (arr[i] < target) { pred = arr[i]; i = 2 * i + 2; }
    else if (arr[i] > target) { i = 2 * i + 1; }
    else { i = 2 * i + 1; }
  }
  return pred;
}

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

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)return i>0?nums[i-1]:-1;}
        return -1;
    }
}