# Inorder Successor in BST

## Intuition

The successor of a node is the next visited node in inorder traversal. So it's either its parent or the left most leaf of its right subtree. So we could get the result by the following algorithm.

First, do a binary search and get the node p. While we do this binary search, we should always save the parent node of current node.

Once we get the node p, we could get the successor of the node by following way. If its right node is None, the successor if its parent. If its right node is not None, it's successor is the left most leaf of its right sub-tree.

## Solution

``````
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
parent = None
node = root
while node and node != p:
if node.val < p.val:
node = node.right
else:
parent = node
node = node.left

if node is None:
return None
if node.right is None:
return parent
else:
successor = node.right
while successor.left:
successor = successor.left
return successor

``````