First, we perform an inorder or Morris traversal of the binary search tree (BST) to visit the nodes in sorted order.
While traversing, we check each node and identify the first node with a value greater than the given key.
Once we find the node with the greater value, we know it is the inorder successor of the given key, so we return this node.

Code

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

// define tree node structure
struct TreeNode {
    // value of the node
    int val;
    // pointer to the left child
    TreeNode* left;
    // pointer to the right child
    TreeNode* right;
    // constructor
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// solution class
class Solution {
public:
    // find inorder successor in BST by tracking candidate
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        // initialize successor pointer
        TreeNode* successor = nullptr;
        // traverse until null
        while (root != nullptr) {
            // move left while updating successor when root > p
            if (root->val > p->val) {
                successor = root;
                root = root->left;
            }
            // otherwise move right
            else {
                root = roo