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


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 not root:
            return None

        self.found = False
        self.ans = None
        self.dfs(root, p)
        return self.ans

    def dfs(self, node, p):
        if not node:
            return

        self.dfs(node.left, p)
        if self.found == True: # next node
            self.ans = node
            self.found = False
        if node == p:
            self.found = True
        self.dfs(node.right, p)