Find the Inorder Predecessor in a Binary Search Tree

Problem Statement❯

Given a Binary Search Tree (BST) and a target node, find the inorder predecessor of the given node. The inorder predecessor of a node is the previous node in the in-order traversal of the BST. If no predecessor exists (i.e., the node is the first in in-order traversal), return null or equivalent.

Examples❯

Input BST	Target Node (p)	Inorder Predecessor	Description
[20, 10, 30, 5, 15, 25, 35]	15	10	10 is the rightmost node in the left subtree of 15 (which has no left child), so the predecessor is its ancestor 10.
[20, 10, 30, 5, 15, 25, 35]	25	20	25 has no left child, and its predecessor is the last ancestor smaller than 25, which is 20.
[20, 10, 30, 5, 15, 25, 35]	10	5	10 has a left child 5, which is its predecessor as it’s the rightmost in the left subtree.
[20, 10, 30, 5, 15, 25, 35]	5	null	5 is the smallest node and has no left subtree or smaller ancestor, so it has no inorder predecessor.
[50, 30, 70, 20, 40, 60, 80]	60	50	60 has no left child; the last smaller ancestor is 50, making it the predecessor.

Solution❯

Understanding the Problem

In a Binary Search Tree (BST), the inorder predecessor of a node is the node that comes immediately before it in the in-order traversal (Left → Root → Right).

We are given a node, and our task is to find its inorder predecessor — the previous node visited if we were walking the BST in in-order order.

We’ll now walk through a clear, beginner-friendly approach to solve this, using a step-by-step method with an example and edge case handling.

Step-by-Step Solution with Example

Step 1: Understand the Inorder Traversal

In-order traversal of a BST always produces the nodes in sorted (ascending) order. So, the inorder predecessor of a given node is the node that appears just before it in this sorted order.

Step 2: Case 1 – Node Has a Left Subtree

If the node has a left child, then its inorder predecessor is the rightmost node in that left subtree.

For example, consider the BST below:


        6
       /       4   8
               5

Let’s say the target node is 6. Since it has a left subtree rooted at 4, we go to 4 and move right until the end. The rightmost node is 5, which is the inorder predecessor.

Step 3: Case 2 – Node Has No Left Subtree

If the node doesn't have a left subtree, we have to look upwards to its ancestors. Specifically, the inorder predecessor is the lowest ancestor of the node, where the node lies in the right subtree.

For example, in this BST:


    1
           2
               3

If our target is node 3, it has no left child. We look at the path from root to 3: 1 → 2 → 3. Among these, 2 is the last node for which 3 was in the right subtree. So, 2 is the inorder predecessor.

Step 4: Case 3 – Node is the Leftmost in the Tree

If the node is the smallest element in the BST (i.e., no node lies before it), then it has no inorder predecessor.

Example:


    1
           2

The inorder predecessor of 1 is null since there’s no node smaller than it in the tree.

Step 5: Traverse and Track Predecessor While Searching

When searching for the node, we can also track the potential predecessor. Every time we move right in the tree (i.e., node.val < target.val), the current node could be a predecessor.

We keep moving down the tree while tracking this until we find the target node.

Edge Cases

Empty Tree

If the tree is empty, there is no node to search. So the predecessor is null.

Single Node Tree

If the tree has only one node and that is the target, there’s no other node to act as predecessor. So the answer is null.

Example: Tree = [5], target = 5 → Output = null.

Node Not Found

If the target node doesn’t exist in the tree, we return null or handle as per the requirement. Always validate the input.

Multiple Nodes with Same Value

In standard BSTs, duplicates are usually not allowed. But if allowed, clarify whether you want the predecessor of the first occurrence or some specific one.

Finally

To find the inorder predecessor in a BST, you need to carefully consider whether the node has a left child or not. Based on that, either go down to the rightmost node in the left subtree or go up to the closest ancestor where the node lies in the right subtree.

Always keep edge cases in mind like null trees, single node trees, and nodes with no predecessors.

Understanding how inorder traversal works helps build strong intuition for solving many binary search tree problems.

Algorithm Steps❯

If the target node has a left subtree, the inorder predecessor is the rightmost node in that left subtree. Traverse to the left child and then keep moving to the right child until no more right children exist.
If the target node does not have a left subtree, traverse up using the parent pointers until you find an ancestor of which the target node is in the right subtree. That ancestor is the inorder predecessor.
If no such ancestor exists, then the target node has no inorder predecessor.

Code

C++

Python

Java

Rust

Kotlin

Swift

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left, *right, *parent;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = node->parent = NULL;
    return node;
}

TreeNode* findInorderPredecessor(TreeNode* node) {
    if (node->left) {
        TreeNode* pred = node->left;
        while (pred->right) pred = pred->right;
        return pred;
    }
    TreeNode* curr = node;
    while (curr->parent && curr == curr->parent->left) {
        curr = curr->parent;
    }
    return curr->parent;
}

int main() {
    TreeNode* root = createNode(20);
    root->left = createNode(10);
    root->right = createNode(30);
    root->left->parent = root;
    root->right->parent = root;
    root->left->right = createNode(15);
    root->left->right->parent = root->left;

    TreeNode* node = root->left->right;
    TreeNode* pred = findInorderPredecessor(node);
    if (pred)
        printf("Inorder predecessor of %d is %d\n", node->val, pred->val);
    else
        printf("No inorder predecessor found\n");

    return 0;
}

⬅ Previous TopicFind the Inorder Successor in a Binary Search Tree

Next Topic ⮕Check if a Binary Tree is a Binary Search Tree

Comments

Loading comments...