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.
It's guaranteed p is one node in the given tree. (You can directly compare the memory address to find p)
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
Solution: (Using Inorder Traversal)
class Solution {
public:
/*
* @param root: The root of the BST.
* @param p: You need find the successor node of p.
* @return: Successor of p.
*/
vector<TreeNode *> v;
void traverse(TreeNode *root){
if(root == NULL){
return;
}
traverse(root->left);
v.push_back(root);
traverse(root->right);
return;
}
TreeNode * inorderSuccessor(TreeNode * root, TreeNode * p) {
// write your code here
if(root == NULL){
return NULL;
}
traverse(root);
int i;
for(i=0;i<v.size();i++){
if(v[i]->val == p->val){
break;
}
}
i++;
if(i == v.size()){
return NULL;
}
return v[i];
}
};
Solution: (Properties of BST)
Approach:
If value is less than root then, root can be the successor and we check for Left Tree
Else we got to right subtree
class Solution {
public:
/*
* @param root: The root of the BST.
* @param p: You need find the successor node of p.
* @return: Successor of p.
*/
TreeNode * inorderSuccessor(TreeNode * root, TreeNode * p) {
// write your code here
TreeNode *t = root;
if(root == NULL){
return NULL;
}
TreeNode *succ = NULL;
while(t!=NULL){
if(p->val< t->val){
succ = t;
t = t->left;
}
else{
t = t->right;
}
}
return succ;
}
};