# 2 approaches to this problem

• 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;
}
};``````

• I think check "leftCandidate->val < root->val" is not necessary.

In my understanding, we are actually looking for the first node that its value is larger than p.val.
So, in case "root->val <= p->val", we will just return the result, but in case "root->val > p->val", we will assign the return value to be the first node that its value is larger than p.val. In later backtrack, if we found the return value has been assigned to a non-null value, we will keep return it even its value is larger than p.val.

Correct me if I am wrong

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.