BiruLyu
8/10/2017 - 10:19 PM

## 285. Inorder Successor in BST(#Morris Predecessor).java

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

// 29 / 29 test cases passed.
// Status: Accepted
// Runtime: 5 ms``````
``````//Just want to share my recursive solution for both getting the successor and predecessor for a given node in BST.

//Successor

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

if (root.val <= p.val) {
return successor(root.right, p);
} else {
TreeNode left = successor(root.left, p);
return (left != null) ? left : root;
}
}
//Predecessor

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

if (root.val >= p.val) {
return predecessor(root.left, p);
} else {
TreeNode right = predecessor(root.right, p);
return (right != null) ? right : root;
}
}``````
``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
TreeNode cur = root, pre = null;
while (cur != null) {
if (cur.left == null) {
if (pre == p) {
return cur;
}
pre = cur;
cur = cur.right;
} else {
TreeNode temp = cur.left;
while (temp.right != null && temp.right != cur) {
temp = temp.right;
}
if (temp.right == null) {
temp.right = cur;
cur = cur.left;
} else {
if (pre == p) {
return cur;
}
temp.right = null;
pre = cur;
cur = cur.right;
}

}
}
return null;
}
}``````
``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
TreeNode cur = root, pre = null;
while (cur != null) {
if (cur.left == null) {
if (cur == p) {
return pre;
}
pre = cur;
cur = cur.right;
} else {
TreeNode temp = cur.left;
while (temp.right != null && temp.right != cur) {
temp = temp.right;
}
if (temp.right == null) {
temp.right = cur;
cur = cur.left;
} else {
if (cur == p) {
return pre;
}
temp.right = null;
pre = cur;
cur = cur.right;
}

}
}
return pre;
}
}``````