A binary search tree is implemented using an array. You are given the index 'i' of the array. You need to find out the next element after array[i] in the inorder traversal
of BST in O(1).
Suppose the BST is
20
/ \
10 30
/ \ / \
5 15 25 35
Array is 20 10 30 5 15 25 35
if ((n is leaf or n has only left child) {
ReplyDeleteif (n is the left child of parent){
then its parent is the successor..
} else { // n is the right child of parent
then go to its parent recursively.. till v reach a node which is a left node of its parent. then the parent of such a node is the successor.
}
}
else {
move to right node and take left till v reach leaf node. then this leaf node is its successor
}
But the above process takes o(logn). We require o(1).