Find the Inorder Predecessor in a Binary Search Tree

Problem and examples

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.

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.

How it works

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.

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.

Implementation and efficiency

C implementation

#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;
}

C++ implementation

#include <iostream>
using namespace std;

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

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 = new TreeNode(20);
    root->left = new TreeNode(10);
    root->right = new TreeNode(30);
    root->left->parent = root;
    root->right->parent = root;
    root->left->right = new TreeNode(15);
    root->left->right->parent = root->left;

    TreeNode* node = root->left->right;
    TreeNode* pred = findInorderPredecessor(node);
    if (pred)
        cout << "Inorder predecessor of " << node->val << " is " << pred->val << endl;
    else
        cout << "No inorder predecessor found" << endl;

    return 0;
}

Python implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None, parent=None):
        self.val = val
        self.left = left
        self.right = right
        self.parent = parent

def find_inorder_predecessor(node):
    if node.left:
        pred = node.left
        while pred.right:
            pred = pred.right
        return pred
    curr = node
    while curr.parent and curr == curr.parent.left:
        curr = curr.parent
    return curr.parent

if __name__ == '__main__':
    root = TreeNode(20)
    root.left = TreeNode(10, parent=root)
    root.right = TreeNode(30, parent=root)
    root.left.right = TreeNode(15, parent=root.left)

    node = root.left.right
    pred = find_inorder_predecessor(node)
    if pred:
        print(f"Inorder predecessor of {node.val} is {pred.val}")
    else:
        print("No inorder predecessor found")

Java implementation

class TreeNode {
    int val;
    TreeNode left, right, parent;
    TreeNode(int v) { val = v; }
}

public class InorderPredecessor {
    public static TreeNode findInorderPredecessor(TreeNode node) {
        if (node.left != null) {
            TreeNode pred = node.left;
            while (pred.right != null) pred = pred.right;
            return pred;
        }
        TreeNode curr = node;
        while (curr.parent != null && curr == curr.parent.left) {
            curr = curr.parent;
        }
        return curr.parent;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(20);
        root.left = new TreeNode(10);
        root.right = new TreeNode(30);
        root.left.parent = root;
        root.right.parent = root;
        root.left.right = new TreeNode(15);
        root.left.right.parent = root.left;

        TreeNode node = root.left.right;
        TreeNode pred = findInorderPredecessor(node);
        if (pred != null)
            System.out.println("Inorder predecessor of " + node.val + " is " + pred.val);
        else
            System.out.println("No inorder predecessor found");
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null, parent = null) {
        this.val = val;
        this.left = left;
        this.right = right;
        this.parent = parent;
    }
}

function findInorderPredecessor(node) {
    if (node.left) {
        let pred = node.left;
        while (pred.right) pred = pred.right;
        return pred;
    }
    let curr = node;
    while (curr.parent && curr === curr.parent.left) {
        curr = curr.parent;
    }
    return curr.parent;
}

let root = new TreeNode(20);
root.left = new TreeNode(10, null, null, root);
root.right = new TreeNode(30, null, null, root);
root.left.right = new TreeNode(15, null, null, root.left);

let node = root.left.right;
let pred = findInorderPredecessor(node);
if (pred)
    console.log(`Inorder predecessor of ${node.val} is ${pred.val}`);
else
    console.log("No inorder predecessor found");

Go implementation

package main

import (
    "fmt"
)

type TreeNode struct {
    val         int
    left, right, parent *TreeNode
}

func findInorderPredecessor(node *TreeNode) *TreeNode {
    if node.left != nil {
        pred := node.left
        for pred.right != nil {
            pred = pred.right
        }
        return pred
    }
    curr := node
    for curr.parent != nil && curr == curr.parent.left {
        curr = curr.parent
    }
    return curr.parent
}

func main() {
    root := &TreeNode{val: 20}
    root.left = &TreeNode{val: 10, parent: root}
    root.right = &TreeNode{val: 30, parent: root}
    root.left.right = &TreeNode{val: 15, parent: root.left}

    node := root.left.right
    pred := findInorderPredecessor(node)
    if pred != nil {
        fmt.Printf("Inorder predecessor of %d is %d\n", node.val, pred.val)
    } else {
        fmt.Println("No inorder predecessor found")
    }
}

Rust implementation

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
    parent: *mut TreeNode,
}

fn main() {
    println!("Inorder predecessor in Rust would require unsafe pointer handling.");
    println!("This demo omits full implementation for brevity and safety.");
}

Kotlin implementation

class TreeNode(var val: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
    var parent: TreeNode? = null
}

fun findInorderPredecessor(node: TreeNode): TreeNode? {
    node.left?.let {
        var pred = it
        while (pred.right != null) pred = pred.right!!
        return pred
    }
    var curr = node
    while (curr.parent != null && curr == curr.parent!!.left) {
        curr = curr.parent!!
    }
    return curr.parent
}

fun main() {
    val root = TreeNode(20)
    root.left = TreeNode(10).also { it.parent = root }
    root.right = TreeNode(30).also { it.parent = root }
    root.left!!.right = TreeNode(15).also { it.parent = root.left }

    val node = root.left!!.right!!
    val pred = findInorderPredecessor(node)
    if (pred != null)
        println("Inorder predecessor of ${node.val} is ${pred.val}")
    else
        println("No inorder predecessor found")
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    weak var parent: TreeNode?
    init(_ val: Int) {
        self.val = val
    }
}

func findInorderPredecessor(_ node: TreeNode) -> TreeNode? {
    if let left = node.left {
        var pred = left
        while let right = pred.right {
            pred = right
        }
        return pred
    }
    var curr: TreeNode? = node
    while let parent = curr?.parent, curr === parent.left {
        curr = parent
    }
    return curr?.parent
}

let root = TreeNode(20)
root.left = TreeNode(10)
root.right = TreeNode(30)
root.left?.parent = root
root.right?.parent = root
root.left?.right = TreeNode(15)
root.left?.right?.parent = root.left

let node = root.left!.right!
if let pred = findInorderPredecessor(node) {
    print("Inorder predecessor of \(node.val) is \(pred.val)")
} else {
    print("No inorder predecessor found")
}

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null = null;
    right: TreeNode | null = null;
    parent: TreeNode | null = null;
    constructor(val: number) {
        this.val = val;
    }
}

function findInorderPredecessor(node: TreeNode): TreeNode | null {
    if (node.left) {
        let pred = node.left;
        while (pred.right) pred = pred.right;
        return pred;
    }
    let curr: TreeNode | null = node;
    while (curr.parent && curr === curr.parent.left) {
        curr = curr.parent;
    }
    return curr.parent;
}

const root = new TreeNode(20);
root.left = new TreeNode(10);
root.left.parent = root;
root.right = new TreeNode(30);
root.right.parent = root;
root.left.right = new TreeNode(15);
root.left.right.parent = root.left;

const node = root.left.right;
const pred = findInorderPredecessor(node);
if (pred)
    console.log(`Inorder predecessor of ${node.val} is ${pred.val}`);
else
    console.log("No inorder predecessor found");