Inorder Successor in BST

Problem: Inorder Successor in BST

We do search from root and push candidate nodes into a stack.

Code in Python:

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

class Solution(object):
    def inorderSuccessor(self, root, p):
        """
        :type root: TreeNode
        :type p: TreeNode
        :rtype: TreeNode
        """
        stack = [root]
        while stack:
            if p.val >= stack[-1].val:
                node = stack.pop()
                if node.right: stack.append(node.right)
            else:
                if not stack[-1].left: return stack[-1]
                stack.append(stack[-1].left)
                stack[-2].left = None
        return None