Flipkart Interview Question
Software Engineer / Developersvoid create_stack(Tree *root, Tree *node, stack *st, int *done)
{
if (root == NULL) return;
if (root == node) {
st.push(root);
done = 1;
return;
}
st.push(root)
crete_stack(root->left, node, st, done)
if(done) return;
crete_stack(root->right, node, st, done)
if(done) return;
st.pop(root)
}
void __findKnode(Tree *node, int k, List * ans)
{
if (node == NULL) return;
if( k == 0) {
append(ans, node);
return;
}
__findKnode(node->left, k-1,ans);
__findKnode(node->right, k-1,ans);
}
void findKnode(Tree *root, Tree *node, int k)
{
List *ans = NULL;
Tree * prev = NULL;
int dist = k
int done = 0
Stack *st;
create_Stack(root, node, st, &done)
while(top = st.pop()){
if (dist < 0)
break;
if(dist == 0){
append(ans, top);
break;
}
if(prev == NULL){
__findKnode(top, dist, ans);
} else if( top->left == prev)
__findKnode(top->right, dist-1, ans);
else
__findKnode(top->left, dist-1, ans);
dist -= 1
prev = top
}
return ans;
}
value = node.data;
min = value-k;
max = value+k;
Now do in/pre/post/leve order traversal of the BT and check if each node.value is in the [min,max] range.
void Tree::getAllNodes(TreeNode *node, TreeNode *prev, int dist, int k){
- Anonymous September 04, 2010if(dist == k){
kdistnodes.push_back(node->val);
return;
}
if(node->left != NULL && node->left != prev){
getAllNodes(node->left, node, dist+1, k);
}
if(node->right != NULL && node->right != prev){
getAllNodes(node->right, node, dist+1, k);
}
if(node->parent != NULL && node->parent != prev){
getAllNodes(node->parent, node, dist+1, k);
}
}