Binary Search Tree Inorder Succesor

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

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

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.