285. Inorder Successor in BST
Description
Given the root of a binary search tree and a node p in it, return the in-order successor of that node in the BST. If the given node has no in-order successor in the tree, return null.
The successor of a node p is the node with the smallest key greater than p.val.
Constraints
The number of nodes in the tree is in the range
[1, 104].-105 <= Node.val <= 105All Nodes will have unique values.
Approach
Links
GeeksforGeeks
Leetcode
ProgramCreek
YouTube
Examples
Input: root = [2, 1, 3], p = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.
Input: root = [5, 3, 6, 2, 4, null, null, 1], p = 6
Output: null
Explanation: There is no in-order successor of the current node, so the answer is null.
Solutions
// 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;
}
}Follow up
Last updated
Was this helpful?