Here is a good explaination I found:
If you have right child, do this approach (case 1 above):
If you don't have a right child, do this approach (case 2 above):
Python solution of iterative and recursive:
#method 1: iterative :
def inorderSuccessor(self,root,p): suc=None while root: # if root.val>p.val: #if root.val=p.val we still move right, cause we need find a value greater than him. #greater value is successor candidate: suc=root root=root.left else: root=root.right return suc
#method 2: recursive:
def inorderSuccessor(self,root,p): if root == None:return None if root.val>p.val:#means root is at right side of p, then move left: suc=self.inorderSuccessor(root.left,p) #suc is none means this is a dead end, and since we are moving left, so successor is the previous one, which is root. if suc !=None: return suc else: return root else: #means root is at right side of p, it could be the successor,if it's left value # Or it could be far right from P, then move left: return self.inorderSuccessor(root.right,p)
I found this page quite useful. Hope it helps!
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.