Inorder Successor in a Binary Search Tree

In this post, we will discuss how to find the Inorder Successor of a given node in a Binary Search Tree (BST). The Inorder Successor of a node is the node that comes immediately after the given node in the in-order traversal of the BST.

Problem Definition

Given a node in a binary search tree, find its in-order successor. If the given node does not have an in-order successor, return NULL.

• The in-order traversal of a binary tree visits the nodes in ascending order (left → root → right).
• The in-order successor of a node is the smallest node that is greater than the given node.

Approach

To find the in-order successor of a node in a BST, we need to consider two cases:

1. The node has a right subtree:
   • The in-order successor is the leftmost (minimum) node in the right subtree.
2. The node does not have a right subtree:
   • We traverse up the tree from the node's parent. The in-order successor is the last ancestor for which the node was in the left subtree.

Steps:

1. If the node has a right subtree:
   • Move to the right child and then find the leftmost node in the right subtree.
2. If the node does not have a right subtree:
   • Move upwards from the node. Traverse up the ancestors until you find a node that is the left child of its parent. That parent will be the in-order successor.

C++ Code Implementation

#include <iostream>
using namespace std;

// Definition for a binary search tree node
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// Helper function to find the leftmost node in a subtree
TreeNode* findMin(TreeNode* node) {
    while (node->left != NULL) {
        node = node->left;
    }
    return node;
}

// Function to find the inorder successor of a given node in BST
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* node) {
    // Case 1: If there is a right subtree, find the min in that subtree
    if (node->right != NULL) {
        return findMin(node->right);
    }

    // Case 2: If no right subtree, find the deepest ancestor for which the node is in the left subtree
    TreeNode* successor = NULL;
    while (root != NULL) {
        if (node->val < root->val) {
            successor = root; // Potential successor
            root = root->left; // Move left
        } else if (node->val > root->val) {
            root = root->right;  // Move right
        } else {
            break;
        }
    }

    return successor;
}

int main() {
    TreeNode* root = new TreeNode(20);
    root->left = new TreeNode(10);
    root->right = new TreeNode(30);
    root->left->left = new TreeNode(5);
    root->left->right = new TreeNode(15);
    root->right->right = new TreeNode(35);

    TreeNode* node = root->left->right;  // Node with value 15

    TreeNode* successor = inorderSuccessor(root, node);

    if (successor != NULL) {
        cout << "Inorder Successor of node " << node->val << " is " << successor->val << endl;
    } else {
        cout << "Inorder Successor of node " << node->val << " does not exist." << endl;
    }

    return 0;
}

Time and Space Complexity

Time Complexity

• Best Case: $O(1)$ - When the successor is the parent or when the node has only a small right subtree.
• Average Case: $O(\log n)$ - For a reasonably balanced tree, finding the minimum in a subtree takes logarithmic time.
• Worst Case: $O(n)$ - When traversing the entire height of a completely skewed tree.

Space Complexity

• $O(1)$ - The iterative approach uses constant space.
• $O(h)$ - If implemented recursively, where $h$ is the height of the tree (at most $n$ for a skewed tree).

Explanation

Finding the inorder successor uses the BST property: if a node has a right subtree, the successor is the minimum node in that subtree. If not, we traverse upward until finding an ancestor where the current path came from the left. The algorithm is efficient on balanced trees but can degrade on skewed structures.