> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/l3er-cha-shu-he-fen-zhi-fa/inorder-successor-in-binary-search-treeff08-zhong-xu-hou-ji-ff09.md).

# Inorder Successor in Binary Search Tree（中序后继）

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

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

## Successor

分析

利用bst左右子树和root大小关系

iterative

```
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode ret = null;
        while(root != null){
            if(root.val > p.val){
                ret = root;
                root = root.left;
            }else{
                root = root.right;
            }
        }

        return ret;
    }
```

recursive

```
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if(root == null)
        return null;
        if(root.val > p.val){
            TreeNode left = inorderSuccessor(root.left, p);
            return left != null ? left : root;
        }else{
            return inorderSuccessor(root.right, p);
        }
    }
```

## Predecessor

iterative

```
public TreeNode predecessor(TreeNode root, TreeNode p) {
    TreeNode ret = null;
    while(root != null){
        if(root.val < p.val){
            ret = root;
            root = root.right;
        }else{
            root = root.left;           
        }
    }
    return ret;
}
```

recursive

```
public TreeNode predecessor(TreeNode root, TreeNode p) {
    if(root == null)
        return null;

    if(root.val < p.val){
        TreeNode right =  predecessor(root.right, p);
        return right != null : right : root;
    }elsel{
        return predecessor(root.left, p);

    }

}
```