Open In App

Inorder predecessor and successor in BST

Last Updated : 11 May, 2025
Comments
Improve
Suggest changes
Like Article
Like
Report
Try it on GfG Practice
redirect icon

Given a BST and a key, the task is to find the in-order successor and predecessor of the given key. In case the given key is not found in BST, then return the two values within which this key will lie.

In the below diagram, successor of 4 is 5 and predecessor is 3. For 1, successor is 3 and there is no predecessor for 1.

1

Table of Content

Using Inorder Traversal - O(n) Time and O(n) Space

The idea is based on the fact that inorder traversal of a BST is always a sorted sequence. We do BST traversal, the first greater value seen is successor and the last smaller value seen is predecessor.

Below is the implementation of the above approach: 

C++ 
// C++ program to find the predecessor and 
// successor of a given key in a BST
#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node *left, *right;
    Node(int x) {
        data = x;
        left = right = nullptr;
    }
};

// Function to find the predecessor and successor
// of a given key in BST
void findPreSuc(Node* root, Node*& pre, Node*& suc, int key) {
  
    // If root is null, return
    if (!root)
        return;

    // Traverse the left subtree
    findPreSuc(root->left, pre, suc, key);

    // The first greater value seen is successor
    if (root->data > key) {        
        if (suc == nullptr || suc->data > root->data)
            suc = root;
    }
  
    // The last smaller value seen is predecessor
    else if (root->data < key)
        pre = root;

    // Traverse the right subtree
    findPreSuc(root->right, pre, suc, key);
}

int main() {
  
    int key = 65;   
  
    // Let us create the following BST
    //          50
    //       /     \
    //      30      70
    //     /  \    /  \
    //   20   40  60   80
    Node *root = new Node(50);
  	root->left = new Node(30);
  	root->right = new Node(70);
  	root->left->left = new Node(20);
  	root->left->right = new Node(40);
  	root->right->right = new Node(80);
  	root->right->left = new Node(60);

    Node* pre = nullptr;
    Node* suc = nullptr;

    findPreSuc(root, pre, suc, key);

    if (pre != nullptr)
        cout << pre->data << " ";
    else
        cout << -1 << " ";

    if (suc != nullptr)
        cout << suc->data << endl;
    else
        cout << -1 << endl;

    return 0;
}
Java 
// Java program to find the predecessor and 
// successor of a given key in a BST

class Node {
    int data;
    Node left, right;
    Node(int x) {
        data = x;
        left = right = null;
    }
}

class GfG {

    // Function to find the predecessor and successor
    // of a given key in BST
    static void findPreSuc(Node root, Node[] pre, Node[] suc, int key) {
      
        // If root is null, return
        if (root == null)
            return;

        // Traverse the left subtree
        findPreSuc(root.left, pre, suc, key);

        // The first greater value seen is successor
        if (root.data > key) {        
            if (suc[0] == null || suc[0].data > root.data)
                suc[0] = root;
        }
      
        // The last smaller value seen is predecessor
        else if (root.data < key)
            pre[0] = root;

        // Traverse the right subtree
        findPreSuc(root.right, pre, suc, key);
    }

    public static void main(String[] args) {
        int key = 65;   

        // Let us create the following BST
        //          50
        //       /     \
        //      30      70
        //     /  \    /  \
        //   20   40  60   80
        Node root = new Node(50);
        root.left = new Node(30);
        root.right = new Node(70);
        root.left.left = new Node(20);
        root.left.right = new Node(40);
        root.right.right = new Node(80);
        root.right.left = new Node(60);

        Node[] pre = new Node[1];
        Node[] suc = new Node[1];

        findPreSuc(root, pre, suc, key);

        if (pre[0] != null)
            System.out.print(pre[0].data + " ");
        else
            System.out.print(-1 + " ");

        if (suc[0] != null)
            System.out.println(suc[0].data);
        else
            System.out.println(-1);
    }
}
Python 
# Python program to find the predecessor and 
# successor of a given key in a BST

class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None

# Function to find the predecessor and successor
# of a given key in BST
def findPreSuc(root, pre, suc, key):

    # If root is null, return
    if not root:
        return

    # Traverse the left subtree
    findPreSuc(root.left, pre, suc, key)

    # The first greater value seen is successor
    if root.data > key:
        if suc[0] is None or suc[0].data > root.data:
            suc[0] = root

    # The last smaller value seen is predecessor
    elif root.data < key:
        pre[0] = root

    # Traverse the right subtree
    findPreSuc(root.right, pre, suc, key)

if __name__ == "__main__":
    key = 65

    # Let us create the following BST
    #          50
    #       /     \
    #      30      70
    #     /  \    /  \
    #   20   40  60   80
    root = Node(50)
    root.left = Node(30)
    root.right = Node(70)
    root.left.left = Node(20)
    root.left.right = Node(40)
    root.right.right = Node(80)
    root.right.left = Node(60)

    pre = [None]
    suc = [None]

    findPreSuc(root, pre, suc, key)

    if pre[0]:
        print(pre[0].data, end=" ")
    else:
        print(-1, end=" ")

    if suc[0]:
        print(suc[0].data)
    else:
        print(-1)
C# 
// C# program to find the predecessor and 
// successor of a given key in a BST
using System;

class Node {
    public int data;
    public Node left, right;
    public Node(int x) {
        data = x;
        left = right = null;
    }
}

class GfG {

    // Function to find the predecessor and successor
    // of a given key in BST
    static void findPreSuc(Node root, ref Node pre, 
    ref Node suc, int key) {
      
        // If root is null, return
        if (root == null)
            return;

        // Traverse the left subtree
        findPreSuc(root.left, ref pre, ref suc, key);

        // The first greater value seen is successor
        if (root.data > key) {        
            if (suc == null || suc.data > root.data)
                suc = root;
        }

        // The last smaller value seen is predecessor
        else if (root.data < key)
            pre = root;

        // Traverse the right subtree
        findPreSuc(root.right, ref pre, ref suc, key);
    }

    static void Main(string[] args) {
        int key = 65;

        // Let us create the following BST
        //          50
        //       /     \
        //      30      70
        //     /  \    /  \
        //   20   40  60   80
        Node root = new Node(50);
        root.left = new Node(30);
        root.right = new Node(70);
        root.left.left = new Node(20);
        root.left.right = new Node(40);
        root.right.right = new Node(80);
        root.right.left = new Node(60);

        Node pre = null, suc = null;

        findPreSuc(root, ref pre, ref suc, key);

        if (pre != null)
            Console.Write(pre.data + " ");
        else
            Console.Write("-1 ");

        if (suc != null)
            Console.WriteLine(suc.data);
        else
            Console.WriteLine("-1");
    }
}
JavaScript 
// JavaScript program to find the predecessor and 
// successor of a given key in a BST
class Node {
    constructor(x) {
        this.data = x;
        this.left = null;
        this.right = null;
    }
}

// Function to find the predecessor and successor
// of a given key in BST
function findPreSuc(root, pre, suc, key) {
  
    // If root is null, return
    if (root === null)
        return;

    // Traverse the left subtree
    findPreSuc(root.left, pre, suc, key);

    // The first greater value seen is successor
    if (root.data > key) {
        if (suc[0] === null || suc[0].data > root.data)
            suc[0] = root;
    }

    // The last smaller value seen is predecessor
    else if (root.data < key) {
        pre[0] = root;
    }

    // Traverse the right subtree
    findPreSuc(root.right, pre, suc, key);
}

let key = 65;

// Let us create the following BST
//          50
//       /     \
//      30      70
//     /  \    /  \
//   20   40  60   80
let root = new Node(50);
root.left = new Node(30);
root.right = new Node(70);
root.left.left = new Node(20);
root.left.right = new Node(40);
root.right.right = new Node(80);
root.right.left = new Node(60);

let pre = [null];
let suc = [null];

findPreSuc(root, pre, suc, key);

if (pre[0] !== null)
    console.log(pre[0].data);
else
    console.log("-1 ");

if (suc[0] !== null)
    console.log(suc[0].data);
else
    console.log(-1);

Output
60 70

Using BST Search - O(h) Time and O(1) Space

We have discussed Successor in BST. We use BST properties to efficiently find inorder successor and predecessor. We follow normal BST search  algorithm. Before finding the given key, the last seen greater value is successor and the last seen smaller value is predecessor.

Follow the steps below to solve the problem:

  • If root is NULL then return.
  • if key is found then
    • If its left subtree is not null, then predecessor will be the right most child of left subtree or left child itself.
    • If its right subtree is not null Then The successor will be the left most child of right subtree or right child itself.
  • If key is smaller than root node set the successor as root search recursively into left subtree.
  • Otherwise set the predecessor as root search recursively into right subtree.

Below is the implementation of the above approach: 

C++ 
// C++ program to find the predecessor and 
// successor of a given key in a BST
#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node *left, *right;
    Node(int x) {
        data = x;
        left = right = nullptr;
    }
};

// Function to find the maximum value in the
// left subtree (Predecessor)
Node *rightMost(Node *node) {
    while (node->right != nullptr) {
        node = node->right;
    }
    return node;
}

// Function to find the minimum value in
// the right subtree (Successor)
Node *leftMost(Node *node) {
    while (node->left != nullptr) {
        node = node->left;
    }
    return node;
}

// This function finds predecessor and successor
// of key in BST. It sets pre and suc as predecesso
// and successor respectively using an iterativ
// e approach.
void findPreSuc(Node *root, Node *&pre, Node *&suc, int key) {
    Node *curr = root;

    while (curr != nullptr) {
        if (curr->data < key) {
            pre = curr;
            curr = curr->right;
        }
        else if (curr->data > key) {
            suc = curr;
            curr = curr->left;
        }
        else {
          
            // Find the predecessor (maximum
            // value in the left subtree)
            if (curr->left != nullptr)
                pre = rightMost(curr->left);

            // Find the successor (minimum
            // value in the right subtree)
            if (curr->right != nullptr)
                suc = leftMost(curr->right);

            break;
        }
    }
}

int main() {
  
    int key = 65;   
  
    // Let us create the following BST
    //          50
    //       /     \
    //      30      70
    //     /  \    /  \
    //   20   40  60   80
    Node *root = new Node(50);
  	root->left = new Node(30);
  	root->right = new Node(70);
  	root->left->left = new Node(20);
  	root->left->right = new Node(40);
  	root->right->right = new Node(80);
  	root->right->left = new Node(60);

    Node* pre = nullptr;
    Node* suc = nullptr;

    findPreSuc(root, pre, suc, key);

    if (pre != nullptr)
        cout << pre->data << " ";
    else
        cout << -1 << " ";

    if (suc != nullptr)
        cout << suc->data << endl;
    else
        cout << -1 << endl;

    return 0;
}
Java 
// C++ program to find the predecessor and 
// successor of a given key in a BST

class Node {
    int data;
    Node left, right;
    Node(int x) {
        data = x;
        left = right = null;
    }
}

class GfG {
    
    // Function to find the maximum value in the
    // left subtree (Predecessor)
    static Node rightMost(Node node) {
        while (node.right != null) {
            node = node.right;
        }
        return node;
    }

    // Function to find the minimum value in
    // the right subtree (Successor)
    static Node leftMost(Node node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    // This function finds predecessor and successor
    // of key in BST. It sets pre and suc as predecesso
    // and successor respectively using an iterativ
    // e approach.
    static void findPreSuc(Node root, Node[] pre, Node[] suc, int key) {
        Node curr = root;

        while (curr != null) {
            if (curr.data < key) {
                pre[0] = curr;
                curr = curr.right;
            }
            else if (curr.data > key) {
                suc[0] = curr;
                curr = curr.left;
            }
            else {
              
                // Find the predecessor (maximum
                // value in the left subtree)
                if (curr.left != null)
                    pre[0] = rightMost(curr.left);

                // Find the successor (minimum
                // value in the right subtree)
                if (curr.right != null)
                    suc[0] = leftMost(curr.right);

                break;
            }
        }
    }

    public static void main(String[] args) {
      
        int key = 65;   
      
        // Let us create the following BST
        //          50
        //       /     \
        //      30      70
        //     /  \    /  \
        //   20   40  60   80
        Node root = new Node(50);
        root.left = new Node(30);
        root.right = new Node(70);
        root.left.left = new Node(20);
        root.left.right = new Node(40);
        root.right.right = new Node(80);
        root.right.left = new Node(60);

        Node[] pre = new Node[1];
        Node[] suc = new Node[1];

        findPreSuc(root, pre, suc, key);

        if (pre[0] != null)
            System.out.print(pre[0].data + " ");
        else
            System.out.print(-1 + " ");

        if (suc[0] != null)
            System.out.println(suc[0].data);
        else
            System.out.println(-1);
    }
}
Python 
# C++ program to find the predecessor and 
# successor of a given key in a BST

class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None

# Function to find the maximum value in the
# left subtree (Predecessor)
def rightMost(node):
    while node.right is not None:
        node = node.right
    return node

# Function to find the minimum value in
# the right subtree (Successor)
def leftMost(node):
    while node.left is not None:
        node = node.left
    return node

# This function finds predecessor and successor
# of key in BST. It sets pre and suc as predecesso
# and successor respectively using an iterativ
# e approach.
def findPreSuc(root, pre, suc, key):
    curr = root

    while curr is not None:
        if curr.data < key:
            pre[0] = curr
            curr = curr.right
        elif curr.data > key:
            suc[0] = curr
            curr = curr.left
        else:
          
            # Find the predecessor (maximum
            # value in the left subtree)
            if curr.left is not None:
                pre[0] = rightMost(curr.left)

            # Find the successor (minimum
            # value in the right subtree)
            if curr.right is not None:
                suc[0] = leftMost(curr.right)

            break

if __name__ == "__main__":
  
    key = 65   
  
    # Let us create the following BST
    #          50
    #       /     \
    #      30      70
    #     /  \    /  \
    #   20   40  60   80
    root = Node(50)
    root.left = Node(30)
    root.right = Node(70)
    root.left.left = Node(20)
    root.left.right = Node(40)
    root.right.right = Node(80)
    root.right.left = Node(60)

    pre = [None]
    suc = [None]

    findPreSuc(root, pre, suc, key)

    if pre[0] is not None:
        print(pre[0].data, end=" ")
    else:
        print(-1, end=" ")

    if suc[0] is not None:
        print(suc[0].data)
    else:
        print(-1)
C# 
// C++ program to find the predecessor and 
// successor of a given key in a BST

using System;

class Node {
    public int data;
    public Node left, right;
    public Node(int x) {
        data = x;
        left = right = null;
    }
}

class GfG {
    
    // Function to find the maximum value in the
    // left subtree (Predecessor)
    static Node rightMost(Node node) {
        while (node.right != null) {
            node = node.right;
        }
        return node;
    }

    // Function to find the minimum value in
    // the right subtree (Successor)
    static Node leftMost(Node node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    // This function finds predecessor and successor
    // of key in BST. It sets pre and suc as predecesso
    // and successor respectively using an iterativ
    // e approach.
    static void findPreSuc(Node root, Node[] pre, Node[] suc, int key) {
        Node curr = root;

        while (curr != null) {
            if (curr.data < key) {
                pre[0] = curr;
                curr = curr.right;
            }
            else if (curr.data > key) {
                suc[0] = curr;
                curr = curr.left;
            }
            else {
              
                // Find the predecessor (maximum
                // value in the left subtree)
                if (curr.left != null)
                    pre[0] = rightMost(curr.left);

                // Find the successor (minimum
                // value in the right subtree)
                if (curr.right != null)
                    suc[0] = leftMost(curr.right);

                break;
            }
        }
    }

    static void Main() {
      
        int key = 65;   
      
        // Let us create the following BST
        //          50
        //       /     \
        //      30      70
        //     /  \    /  \
        //   20   40  60   80
        Node root = new Node(50);
        root.left = new Node(30);
        root.right = new Node(70);
        root.left.left = new Node(20);
        root.left.right = new Node(40);
        root.right.right = new Node(80);
        root.right.left = new Node(60);

        Node[] pre = new Node[1];
        Node[] suc = new Node[1];

        findPreSuc(root, pre, suc, key);

        if (pre[0] != null)
            Console.Write(pre[0].data + " ");
        else
            Console.Write(-1 + " ");

        if (suc[0] != null)
            Console.WriteLine(suc[0].data);
        else
            Console.WriteLine(-1);
    }
}
JavaScript 
// C++ program to find the predecessor and 
// successor of a given key in a BST

class Node {
    constructor(x) {
        this.data = x;
        this.left = null;
        this.right = null;
    }
}

// Function to find the maximum value in the
// left subtree (Predecessor)
function rightMost(node) {
    while (node.right != null) {
        node = node.right;
    }
    return node;
}

// Function to find the minimum value in
// the right subtree (Successor)
function leftMost(node) {
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

// This function finds predecessor and successor
// of key in BST. It sets pre and suc as predecesso
// and successor respectively using an iterativ
// e approach.
function findPreSuc(root, pre, suc, key) {
    let curr = root;

    while (curr != null) {
        if (curr.data < key) {
            pre[0] = curr;
            curr = curr.right;
        }
        else if (curr.data > key) {
            suc[0] = curr;
            curr = curr.left;
        }
        else {
          
            // Find the predecessor (maximum
            // value in the left subtree)
            if (curr.left != null)
                pre[0] = rightMost(curr.left);

            // Find the successor (minimum
            // value in the right subtree)
            if (curr.right != null)
                suc[0] = leftMost(curr.right);

            break;
        }
    }
}

let key = 65;   
  
// Let us create the following BST
//          50
//       /     \
//      30      70
//     /  \    /  \
//   20   40  60   80
let root = new Node(50);
root.left = new Node(30);
root.right = new Node(70);
root.left.left = new Node(20);
root.left.right = new Node(40);
root.right.right = new Node(80);
root.right.left = new Node(60);

let pre = [null];
let suc = [null];

findPreSuc(root, pre, suc, key);

if (pre[0] != null)
    process.stdout.write(pre[0].data + " ");
else
    process.stdout.write(-1 + " ");

if (suc[0] != null)
    console.log(suc[0].data);
else
    console.log(-1);

Output
60 70

Next Article
Find if there is a triplet in a Balanced BST that adds to zero

A

algoLover
Improve
Article Tags :
Practice Tags :

Similar Reads

We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox
  翻译：