[LintCode] Problem 448 - Inorder Successor in BST

Posted on | In ,

Given a 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.

Note

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

Example

No.1

Input: {1,#,2}, node with value 1

Output: 2

Explanation:

1
2
3
1
 \
  2

No.2

Input: {2,1,3}, node with value 1

Output: 2

Explanation: 

1
2
3
  2
 / \
1   3

Challenge

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

Code

1
2
3
4
5
6
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
1
2
3
4
5
6
7
8
9
10
11
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    if (root == null)
        return null;

    if (root.val <= p.val)
        return inorderSuccessor(root.right, p);
    else {
        TreeNode node = inorderSuccessor(root.left, p);
        return node == null ? root : node;
    }
}