public class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if(p != null && p.right != null) {
TreeNode cur = p.right;
while(cur.left != null) {
cur = cur.left;
}
return cur;
}
TreeNode next = findNext(root, p);
return next;
}
public TreeNode findNext(TreeNode root, TreeNode p) {
if(root == p) {
return null;
}
if(root.val < p.val) {
return findNext(root.right, p);
} else {
TreeNode left = findNext(root.left, p);
return findNext(root.left, p) == null ? root : left;
}
}
}
Java O(lgN) solution


@StefanPochmann this solution is O(log n) only if the tree is balanced correct?? else the solution is O(log h) right?

