bst_successor

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

def successor(node):
    # return the tree node which is the successor of this node
    if node.right:
        node = node.right
        while node.left:
            node = node.left
        return node
    else:
        while node.parent and node.parent.left != node:
            node = node.parent
        return node.parent