285. Inorder Successor in BST
Last updated
Last updated
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}/**
* Time complexity : O(N)
* Space complexity : O(N)
*/
class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if(root == null || p == null) {
return null;
}
if(root == p) {
return root.right;
}
Stack<TreeNode> stack = new Stack();
TreeNode curr = root;
while(!stack.isEmpty() || curr != null) {
while(curr != null) {
stack.push(curr);
curr = curr.left;
}
TreeNode temp = stack.pop();
curr = temp.right;
if(temp == p) {
if(temp.right != null) {
TreeNode m = temp.right;
while(m.left != null) {
m = m.left;
}
return m;
} else if(!stack.isEmpty()) {
return stack.pop();
}
}
}
return null;
}
}/**
* Time complexity : O(N) since we might end up encountering a skewed tree
* and in that case, we will just be discarding one node at a time.
* For a balanced binary-search tree, however, the time complexity
* will be O(logN) which is what we usually find in practice.
* Space complexity : O(1)
*/
class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
TreeNode successor = null;
while (root != null) {
if (p.val >= root.val) {
root = root.right;
} else {
successor = root;
root = root.left;
}
}
return successor;
}
}