> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/trees/inorder-successor-in-bst.md).

# Inorder Successor in BST

Given a binary search tree ([See Definition](http://www.lintcode.com/problem/validate-binary-search-tree/)) and a node in it, find the in-order successor of that node in the BST.

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

It's guaranteed *p* is one node in the given tree. (You can directly compare the memory address to find p)

#### Example

**Example 1:**

```
Input: {1,#,2}, node with value 1
Output: 2
Explanation:
  1
   \
    2
```

**Example 2:**

```
Input: {2,1,3}, node with value 1
Output: 2
Explanation: 
    2
   / \
  1   3
```

[Binary Tree Representation](https://www.lintcode.com/help/binary-tree-representation/)

#### Challenge

O(h), where h is the height of the BST.

```java
public class Solution {
    TreeNode lastLeft;
    TreeNode ans;

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        helper(root, p);
        return ans;
    }

    public void helper(TreeNode root, TreeNode target) {
        if (root == null)
            return;
        if (root == target) {
            // Case 1 -> if right subtree exists ,
            // then ans is smallest node from that subtree
            if (root.right != null) {
                TreeNode temp = root.right;
                while (temp.left != null)
                    temp = temp.left;
                ans = temp;
            }
            // Else the answer is the node where we took the last left turn
            // to reach target node
            else
                ans = lastLeft;
        } else {
            if (target.val > root.val)
                helper(root.right, target);
            else {
                lastLeft = root;
                helper(root.left, target);
            }
        }
    }
}
```