# Binary Search Tree Inorder Succesor

Harshit Jindal Dec 26, 2022 Feb 19, 2021

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

## Complexity of Inorder Successor in BST Algorithm

### 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.

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.