Inorder Successor in BST – Python 3 (Week 12 – 15)

class Solution:
“””
@param: root: The root of the BST.
@param: p: You need find the successor node of p.
@return: Successor of p.
“””
def inorderSuccessor(self, root, p):
# write your code here
if root == None or p == None:
return None
if root.val <= p.val:
return self.inorderSuccessor(root.right, p)
else:
leftAns = self.inorderSuccessor(root.left, p)
return root if leftAns == None else leftAns

Time O(h). Space O(h).