# Inorder Successor in Binary Search Tree

Note: If the given node has no in-order successor in the tree, return null.

这道题让我们求二叉搜索树的某个节点的中序后继节点，那么我们根据BST的性质知道其中序遍历的结果是有序的， 是我最先用的方法是用迭代的中序遍历方法，然后用一个bool型的变量b，初始化为false，我们进行中序遍历，对于遍历到的节点，我们首先看如果此时b已经为true，说明之前遍历到了p，那么此时我们返回当前节点，如果b仍为false，我们看遍历到的节点和p是否相同，如果相同，我们此时将b赋为true，那么下一个遍历到的节点就能返回了，参见代码如下：

## Solution

最简单的方法就是先做一个递归的中序遍历，然后一个公共变量parent。

While 循环

```
class Solution(object):
    """
    @param root <TreeNode>: The root of the BST.
    @param p <TreeNode>: You need find the successor node of p.
    @return <TreeNode>: Successor of p.
    """
    def inorderSuccessor(self, root, p):
        if root is None or p is None:
            return None

        successor = None
        while root is not None and root.val != p.val: #p点的后继节点一定就是root.val > p.val
            if root.val > p.val:
                successor = root
                root = root.left
            else:
                root = root.right

        if root is None: #找不到p点的时候，跳出
            return None

        if root.right is None: #如果没有右节点，当前节点p==root 那么直接返回后续节点，就是从root过来的
            return successor

        root = root.right
        while root.left is not None: #如果有右节点，当前节点p==root 那么p点的后续是右子树的最小值，也就是最左左节点。
            root = root.left

        return root
```

Traverse: Traverse不需要返回任何，而是在不停的设置全局变量。常犯错误，默认写成了前序遍历，实际上是中序遍历。

```
class Solution(object):
    def inorderSuccessor(self, root, p):
        """
        :type root: TreeNode
        :type p: TreeNode
        :rtype: TreeNode
        """
        self.successor = None
        self.ancestor = None
        if root == None or p == None:
            return None
        self.inorderSuccessorHelper(root, p)
        return self.successor
    def inorderSuccessorHelper(self, root, p):
        if root == None:
            return
        self.inorderSuccessorHelper(root.left, p)
        if self.ancestor == p:
            self.successor = root
        self.ancestor = root
        self.inorderSuccessorHelper(root.right, p)
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://liuxue2010.gitbook.io/data-structure-and-algorithms/binary-tree-and-divide-conquer/inorder-successor-in-binary-search-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.