# C++ Solution with long code with O(n) Time Complexity

• ``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
if(!root || !p)
return NULL;
TreeNode *ans = NULL;
bool find_p = false;
parent_nd = NULL;
dfs(root, NULL, p, find_p);
if(!find_p)
return ans;
if(!parent_nd){
if(!root->right)
return ans;
else{
ans = root->right;
while(ans->left){
ans = ans->left;
}
return ans;
}
}else{
if(parent_nd->left == p){
if(p->right == NULL)
return parent_nd;
else{
ans = p->right;
while(ans->left){
ans = ans->left;
}
return ans;
}
}else{
if(root->val < p->val){
if(p->right == NULL)
return ans;
else{
ans = p->right;
while(ans->left){
ans = ans->left;
}
return ans;
}
}else{
if(root == parent_nd)
return ans;
ans = root;
while(ans->left->val > p->val)
ans = ans->left;
return ans;
}
}
}
}

private:
void dfs(TreeNode* cur, TreeNode* parent, TreeNode* p, bool &find_p){
if(cur == p){
find_p = true;
parent_nd = parent;
return ;
}
if(cur->left){
dfs(cur->left, cur, p, find_p);
if(find_p)
return ;
}
if(cur->right){
dfs(cur->right, cur, p, find_p);
if(find_p)
return ;
}
}
private:
TreeNode* parent_nd;
};``````

• O(lgn) is impossible. The desired node might be at depth n (I'm assuming with n you mean the number of nodes).

• Oh, Yes, you are right. Thank you for telling me that!

• This post is deleted!

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