A frequently asked question is: Find the next in order successor in a BST.
Algorithm would be:
If (node has a rightChild){
find min in right subtree i.e. go right and keep going left
till you encounter a NULL
}
else if (node is a leftChild of its parent){
parent is the in order successor
}
else{
node is the right Child.
while(parent != NULL){
1. Keep going up the parents till you find a node that is
the left child of its parent. That parent is the in order successor
or 2. Keep going up till you find a node >= current node
}
if no successor found this means that the node was the rightmost
one and has no successor
}
As an example:
Tree:
30
20 42
10 27 37 45
2 15 22 39 44 50
Third case(node is rt child) needs elaboration:
E.g. Say node is 27, keep going up till you find a node >= 27 i.e. 30, this is the ans
E.g. Node is 15, go up till you find a node that is left child, node is 10, its parent i.e 20
is the required ans
Algorithm would be:
If (node has a rightChild){
find min in right subtree i.e. go right and keep going left
till you encounter a NULL
}
else if (node is a leftChild of its parent){
parent is the in order successor
}
else{
node is the right Child.
while(parent != NULL){
1. Keep going up the parents till you find a node that is
the left child of its parent. That parent is the in order successor
or 2. Keep going up till you find a node >= current node
}
if no successor found this means that the node was the rightmost
one and has no successor
}
As an example:
Tree:
30
20 42
10 27 37 45
2 15 22 39 44 50
Third case(node is rt child) needs elaboration:
E.g. Say node is 27, keep going up till you find a node >= 27 i.e. 30, this is the ans
E.g. Node is 15, go up till you find a node that is left child, node is 10, its parent i.e 20
is the required ans
No comments:
Post a Comment