Problem Statement

Given the root node of a binary search tree (BST) and an integer key. Return the Inorder predecessor and successor of the given key from the provided BST.

If predecessor or successor is missing the return -1.

Examples

Example 1:

Input: root = [5, 2, 10, 1, 4, 7, 12], key = 10
Output: [7, 12]

Example 2:

Input: root = [5, 2, 10, 1, 4, 7, 12], key = 12
Output: [10, -1]

Different Approaches

1️⃣ Brute Force Approach

Intuition:

To find the successor of a given node in a Binary Search Tree (BST), an efficient approach involves performing an in-order traversal of the tree. This traversal generates a sorted list of node values due to the inherent properties of BSTs. Once the sorted list is obtained, a binary search can be conducted on this list to identify the first value greater than the given key, which will be the successor. If the given key is the maximum value in the BST, it will be the last node in the in-order traversal, and hence, the successor does not exist.

Algorithm:

1. Traverse the BST in an in-order manner (Left, Root, Right).
2. During the traversal, store each node's value in a list. This ensures that the list is sorted in ascending order.
3. After completing the in-order traversal, the list will contain the BST's node values in sorted order.
4. Perform a binary search on this sorted list to find the first value greater than the given key.
5. If such a value is found, it is the successor of the given key. Return this value.
6. If no such value exists (i.e., the key is the maximum value in the BST), return null.

Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int data;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
 * };
 **/

class Solution {
public:
    // STEP 1: Perform inorder traversal to get a sorted list of BST values
    void inorder(vector<int>& sortedVals, TreeNode* node) {
        if (node != nullptr) {
            inorder(sortedVals, node->left);          // Traverse left subtree
            sortedVals.push_back(node->data);         // Visit current node
            inorder(sortedVals, node->right);         // Traverse right subtree
        }
    }

    vector<int> succPredBST(TreeNode* root, int key) {
        vector<int> inorderList;

        // STEP 2: Get sorted values of the BST using inorder traversal
        inorder(inorderList, root);

        int pred = -1;  // To store predecessor (largest value < key)
        int succ = -1;  // To store successor (smallest value > key)

        // STEP 3: Binary search for predecessor
        // Predecessor is the greatest value strictly less than key
        int left = 0, right = inorderList.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (inorderList[mid] < key) {
                pred = inorderList[mid];     // Possible predecessor found
                left = mid + 1;              // Move right to find a bigger one
            } else {
                right = mid - 1;             // Move left
            }
        }

        // STEP 4: Binary search for successor
        // Successor is the smallest value strictly greater than key
        left = 0, right = inorderList.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (inorderList[mid] > key) {
                succ = inorderList[mid];     // Possible successor found
                right = mid - 1;             // Move left to find a smaller one
            } else {
                left = mid + 1;              // Move right
            }
        }

        // STEP 5: Return both values as a pair in a vector
        return {pred, succ};
    }
};

Complexity Analysis:

• Time Complexity:O(N), where N is the number of nodes in the binary search tree. The inorder traversal visits each node once, and the subsequent for loop also iterates over the nodes.
• Space Complexity:O(N), where N is the number of nodes in the binary search tree. The sortedList array stores all the node values, resulting in a linear space complexity.

2️⃣ Better Approach

Intuition:

An optimized approach to finding the inorder successor in a Binary Search Tree (BST) involves performing an inorder traversal while keeping track of the first node with a value greater than the given key. The properties of BSTs ensure that an inorder traversal yields node values in ascending order, making it straightforward to identify the next node value following a given key. This method leverages the structure of BSTs to efficiently determine the inorder successor without requiring additional data structures.

Algorithm:

1. Begin by performing an inorder traversal of the Binary Search Tree (BST), which can be done using traditional methods or the Morris Inorder Traversal technique for optimized space complexity.
2. During the traversal, continuously monitor each node, and identify the first node whose value is greater than the specified key.
3. The node identified in the previous step is the inorder successor of the given key. Once this node is found, return it as the result.

Code:

#include <bits/stdc++.h>
using namespace std;

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

class Solution {
public:
    vector<int> succPredBST(TreeNode* root, int key) {
        vector<int> result;
        TreeNode* succ = nullptr;
        TreeNode* pred = nullptr;

        while (root != nullptr) {
            if (root->data == key) {
                // If the key is found, find the predecessor and successor
                if (root->right != nullptr) {
                    succ = findMin(root->right);
                }
                if (root->left != nullptr) {
                    pred = findMax(root->left);
                }
                break;
            } else if (root->data < key) {
                // If current node's value is less than key, move to the right subtree
                pred = root;
                root = root->right;
            } else {
                // If current node's value is greater than key, move to the left subtree
                succ = root;
                root = root->left;
            }
        }

        if (pred != nullptr) {
            result.push_back(pred->data);
        } else {
            result.push_back(-1); // or handle differently if predecessor not found
        }

        if (succ != nullptr) {
            result.push_back(succ->data);
        } else {
            result.push_back(-1); // or handle differently if successor not found
        }

        return result;
    }

private:
    // Helper function to find the minimum value node in a subtree
    TreeNode* findMin(TreeNode* node) {
        while (node->left != nullptr) {
            node = node->left;
        }
        return node;
    }

    // Helper function to find the maximum value node in a subtree
    TreeNode* findMax(TreeNode* node) {
        while (node->right != nullptr) {
            node = node->right;
        }
        return node;
    }
};

int main() {
    // Example usage
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(3);
    root->right = new TreeNode(8);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(4);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(9);

    Solution sol;
    vector<int> result = sol.succPredBST(root, 4);

    cout << "Predecessor: " << result[0] << ", Successor: " << result[1] << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity:O(H), explanation in few words: where H is the height of the BST.
• Space Complexity:O(1), explanation in few words: since only a constant amount of space is used.

3️⃣ Optimal Approach

Intuition:

This approach takes advantage of the unique properties of a Binary Search Tree (BST) to efficiently find an element's successor. The BST's structure allows quick navigation based on node values. To find the successor of a given node, a variable 'successor' is initialized to null. As the tree is traversed, any value greater than the given key is tracked. When such a value is found, 'successor' is updated to be the smaller of the current 'successor' and the newly encountered value.

Algorithm:

1. Initialize a variable 'successor' to a very high value (e.g., the maximum integer value).
2. Traverse the BST
   1. Start at the root of the BST and compare the key with the current node's value.
   2. If the current node's value is smaller than the key, move to the right child because the successor must be in the right subtree.
   3. If the current node's value is greater than the key, update 'successor' to be the smaller value between the current 'successor' and the current node's value, then move to the left child because the successor could be in the left subtree.
3. Repeat the above steps until reaching a null node. At the end of the traversal, 'successor' will hold the value of the inorder successor of the given key if it exists; otherwise, it remains as the initial very high value.
4. Check if 'successor' is still the initial high value. If it is, return null (indicating no successor exists). Otherwise, return 'successor'.

Code:

#include <bits/stdc++.h>
using namespace std;

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector< int > succPredBST(TreeNode* root, int key) {
        int predecessor = -1;
        int successor = numeric_limits< int >::max();
        
        // Lambda function to traverse the tree and find successor and predecessor
        function< void(TreeNode*) > traverse = [&](TreeNode* node) {
            if (node == nullptr) {
                return;
            }

            if (node->data < key) {
                // Update predecessor and move to the right subtree
                predecessor = max(predecessor, node->data);
                traverse(node->right);
            } else if (node->data > key) {
                // Update successor and move to the left subtree
                successor = min(successor, node->data);
                traverse(node->left);
            } else {
                // If node's value equals key, find predecessor and successor in subtrees
                if (node->left != nullptr) {
                    // Find maximum value in left subtree for predecessor
                    TreeNode* temp = node->left;
                    while (temp->right != nullptr) {
                        temp = temp->right;
                    }
                    predecessor = temp->data;
                }

                if (node->right != nullptr) {
                    // Find minimum value in right subtree for successor
                    TreeNode* temp = node->right;
                    while (temp->left != nullptr) {
                        temp = temp->left;
                    }
                    successor = temp->data;
                }
            }
        };

        traverse(root);

        // Return the result as a vector with predecessor and successor
        return {
            predecessor == -1 ? -1 : predecessor, 
            successor == numeric_limits< int >::max() ? -1 : successor
        };
    }
};
// Example usage
#include <iostream>
int main() {
    // Create the BST
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(2);
    root->right = new TreeNode(10);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(4);
    root->right->left = new TreeNode(7);
    root->right->right = new TreeNode(12);
    
    // Create Solution object and get the predecessor and successor
    Solution sol;
    vector<int> result = sol.succPredBST(root, 10);
    cout << "[" << result[0] << ", " << result[1] << "]" << endl;  // Output: [7, 12]
    
    return 0;
}

Complexity Analysis:

• Time Complexity: O(N), traversing the binary tree once where N is the number of nodes.
• Space Complexity:O(1), using a constant amount of space to store the predecessor, successor, and temporary variables.