BST Inorder Predecessor in DSA C++

Mental Model

The inorder predecessor of a node in a BST is the node with the next smaller value, found by going left once and then right as far as possible.

Analogy: Imagine a sorted list of books on a shelf. To find the book just before a given one, you look to the left shelf and then pick the rightmost book there.

      20
     /  \
   10    30
  /  \     
 5   15    
       
↑ current node: 15

Dry Run Walkthrough

Input: BST: 20 -> 10 -> 30 -> 5 -> 15; find inorder predecessor of node 15

Goal: Find the node with the largest value smaller than 15

Step 1: Start at node 15, check if it has left child

20 -> 10 -> 30 -> 5 -> [15↑]

Why: We look left to find smaller values

Step 2: Node 15 has no left child, so move up to parent 10

20 -> [10↑] -> 30 -> 5 -> 15

Why: No left subtree means predecessor is an ancestor smaller than 15

Step 3: Since 15 > 10, 10 is candidate predecessor

20 -> [10↑] -> 30 -> 5 -> 15

Why: We track last node smaller than 15 while moving up

Step 4: Move up to 20, which is greater than 15, stop

[20↑] -> 10 -> 30 -> 5 -> 15

Why: 20 is larger, so predecessor is last smaller node 10

Result:

Inorder predecessor of 15 is 10

Annotated Code

DSA C++

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node* parent;
    Node(int v) : val(v), left(nullptr), right(nullptr), parent(nullptr) {}
};

Node* insert(Node* root, int val, Node* parent = nullptr) {
    if (!root) {
        Node* n = new Node(val);
        n->parent = parent;
        return n;
    }
    if (val < root->val) {
        root->left = insert(root->left, val, root);
    } else {
        root->right = insert(root->right, val, root);
    }
    return root;
}

Node* maximum(Node* node) {
    while (node->right) {
        node = node->right; // go right as far as possible
    }
    return node;
}

Node* inorderPredecessor(Node* node) {
    if (!node) return nullptr;
    if (node->left) {
        // predecessor is max in left subtree
        return maximum(node->left);
    }
    // else go up until node is right child of parent
    Node* p = node->parent;
    while (p && node == p->left) {
        node = p;
        p = p->parent; // move up
    }
    return p;
}

void printNode(Node* node) {
    if (node) cout << node->val << "\n";
    else cout << "No predecessor\n";
}

int main() {
    Node* root = nullptr;
    root = insert(root, 20);
    root = insert(root, 10);
    root = insert(root, 30);
    root = insert(root, 5);
    root = insert(root, 15);

    // find node 15
    Node* curr = root->left->right; // 15
    Node* pred = inorderPredecessor(curr);
    printNode(pred);
    return 0;
}

while (node->right) { node = node->right; }

go right as far as possible to find max in left subtree

if (node->left) { return maximum(node->left); }

if left subtree exists, predecessor is max node there

while (p && node == p->left) { node = p; p = p->parent; }

move up until node is right child of parent to find predecessor

return p;

return found predecessor or nullptr if none

Output

10

Complexity Analysis

Time: O(h) because we traverse up or down the tree height h at most once

Space: O(1) because we use only a few pointers, no extra data structures

vs Alternative: Naive approach would do inorder traversal O(n) to find predecessor, this is faster using BST properties

Edge Cases

Node has no left subtree and is the smallest node

No predecessor found, returns nullptr

DSA C++

while (p && node == p->left) { node = p; p = p->parent; }

Node has left subtree

Predecessor is maximum node in left subtree

DSA C++

if (node->left) { return maximum(node->left); }

Node is null

Returns nullptr safely

DSA C++

if (!node) return nullptr;

When to Use This Pattern

When asked to find the previous smaller element in a BST in sorted order, use the inorder predecessor pattern by checking left subtree or moving up ancestors.

Common Mistakes

Mistake: Trying to find predecessor by always going left without checking rightmost node in left subtree
Fix: Go left once, then go right as far as possible to find maximum in left subtree

Mistake: Not moving up ancestors when no left subtree exists
Fix: Traverse up parents until current node is right child of parent

Summary

Finds the node with the next smaller value than a given node in a BST.

Use when you need the previous element in sorted order in a BST.

If left subtree exists, predecessor is max there; else move up until node is right child.