I figured out the naive approach first.....

time complexity : O(n) n is the size of the tree nodes

space complexity: O(n)

```
class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
//special case
if(root == nullptr || (root->left == nullptr && root->right == nullptr))
{
return nullptr;
}
vector<TreeNode*> res;
stack<TreeNode*> stk;
while(!stk.empty() || root != nullptr)
{
if(root != nullptr)
{
stk.push(root);
root = root->left;
}
else
{
root = stk.top();
stk.pop();
if(!res.empty() && p == res.back())
{
return root;
}
res.push_back(root);
root = root->right;
}
}
return nullptr;
}
};
```

And The code below is a more efficient algorithm with explanation

time complexity : O(log(n)) n is the size of the tree nodes

space complexity: O(1)

```
class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
if(root == nullptr)
{
return nullptr;
}
// if the p's value is greater than root's, run the recursive function directly.
//because root could not be the successor of p
if(root->val <= p->val)
{
return inorderSuccessor(root->right, p);
}
//if the p's value is less than root's, run the recursive function first
//Then compare the values between leftCandidate and root, choose the smaller one.
TreeNode* leftCandidate = inorderSuccessor(root->left, p);
return leftCandidate != nullptr && leftCandidate->val < root->val ? leftCandidate : root;
}
};
```