Binary Search Tree Inorder Succesor

  1. Inorder Successor in BST Algorithm
  2. Inorder Successor in BST Illustration
  3. Inorder Successor in BST Implementation
  4. Inorder Successor in BST Algorithm Complexity

The inorder successor of a binary tree is the node that comes next in the binary tree’s inorder traversal. So, it is NULL for the last node inside the tree. Since the inorder traversal of Binary Search Tree is a sorted array. The node with the smallest key greater than the given node is defined as its inorder successor. In a BST, there are two possibilities for the inorder successor, the node with the least value in the node’s right subtree or ancestor. Otherwise, the inorder successor for the node does not exist.

Inorder Successor in BST Algorithm

  • If root == NULL, then set succ as NULL and return.
  • If root->data < current->data, then succ as current and current as current->left.
  • If root->data > current->data, current as current->right.
  • If root->data == current->data and root->right != NULL, succ = minimum(current->right).
  • return succ.

Inorder Successor in BST Illustration

binary search tree

The inorder successor of 3 is 4 because 3 has a right node and 4 is the smallest node that is larger than 3 in the right subtree.

The inorder successor of 4 is 5 because 4 has no right node, and we have to look at its ancestors and among them, 5 is the smallest node that is larger than 4.

Inorder Successor in BST Implementation

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node *left, *right;
    Node(int x) {
        this->data = x;
        this->left = this->right = NULL;
    }
};

Node* insert(Node* root, int key)
{
    if (root == NULL) {
        return new Node(key);
    }
    if (key < root->data) {
        root->left = insert(root->left, key);
    }
    else {
        root->right = insert(root->right, key);
    }
    return root;
}

Node* getNextleft(Node* root)
{
    while (root->left) {
        root = root->left;
    }

    return root;
}

void inorderSuccessor(Node* root, Node*& succ, int key)
{

    if (root == NULL) {
        succ = NULL;
        return;
    }

    if (root->data == key)
    {
        if (root->right) {
            succ = getNextleft(root->right);
        }
    }

    else if (key < root->data)
    {
        succ = root;
        inorderSuccessor(root->left, succ, key);
    }
    else {
        inorderSuccessor(root->right, succ, key);
    }
}

int main()
{
    int keys[] = { 1, 5, 8, 2, 6, 3, 7, 4 };
    Node* root = NULL;
    for (int key : keys) {
        root = insert(root, key);
    }
    for (int key : keys)
    {
        Node* prec = NULL;
        inorderSuccessor(root, prec, key);
        if (prec) {
            cout << "Inorder successor of node " << key << " is " << prec->data;
        }
        else {
            cout << "No inorder Successor of node " << key;
        }

        cout << '\n';
    }

    return 0;
}

Inorder Successor in BST Algorithm Complexity

Time Complexity

  • Average Case

On average-case, the time complexity of finding an inorder successor in a BST is of the order of height of the binary search tree. On average, the height of a BST is O(logn). It occurs when the BST formed is a balanced BST. Hence the time complexity is of the order of [Big Theta]: O(logn).

  • Best Case

The best-case occurs when the tree is a balanced BST. The best-case time complexity of deletion is of the order of O(logn). It is the same as average-case time complexity.

  • Worst-Case

In the worst-case, we might have to traverse from root to the deepest leaf node i.e. the whole height h of the tree. If the tree is unbalanced, i.e. it is skewed, the tree’s height may become n, and hence the worst-case time complexity of both insert and search operation is O(n).

Space Complexity

The algorithm’s space complexity is O(h) due to the extra space required by recursion calls.

Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.

Related Article - Data Structure

  • Linked List
  • Binary Search Tree Check
  • Related Article - Binary Tree

  • Binary Search Tree Delete
  • Binary Search Tree Check
  • Related Article - Binary Search Tree

  • Binary Search Tree Iterative Insert
  • Binary Search Tree Check