|
Given a BST, print all nodes lying between two values ......
Microsoft Interview Questions and Answers
(Continued from previous question...)
138. Given a BST, print all nodes lying between two values ......
Question:
Given a BST, print all nodes lying between two values, inclusive of these values. Write test cases for same.
maybe an answer:
print elements in a BST between min. and max.
pseudo code
Print(BST root, int min, int max) {
insert(root, min);
while(min->successor < max) {
print("%d", min->successor);
min = min->successor;
}
}
In the code above, min->successor means the successor of the node whose key is equal to min.
The code below is to find the successor of the current node "nd"
node *findMin(node *nd) {
while (nd->left) {
nd = nd->left;
}
return nd;
}
node *successor(node *nd) {
if (nd->right) {
return findMin(nd->right);
}
node *y = nd->parent;
while (y && y->right == nd) {
nd = y;
y = y->parent;
}
return y;
}
(Continued on next question...)
Other Interview Questions
| 