CareerCup

int FindMin(Node n, int depth) {
if (n == null) return int.MAX_VALUE;
if (depth == 0) return n.value;

int left = FindMin(n.left, depth - 1);
int right = FindMin(n.right, depth - 1);
return Math.Min(left, right);
}

breadth first traversal ???

breadth first search is better to do this and easy :)
void BreadthFirst(struct node *T,int level)
{
Queue q1,q2;
int c=0,int le=0;
int min=INT_MAX;
if(!T)
return;

enquee(q1,T);
while(!isEmpty(q1)||!isEmpty(q2))
{
while(!isEmpty(q1))
{
if(le==level && c==0)
break;
if(c==0)
{
c=1;
le++;
}
temp=Dequee(q1);
if(temp->left)
enquee(q2,temp->left);
if(temp->right)
enquee(temp->right);
}
c=0;
if(le==level)
break;
while(!isEmpty(q2))
{
if(le==level && c==0)
break;
if(c==0)
{
c=1;
le++;
}
temp=Dequee(q2);
if(temp->left)
enquee(q1,temp->left);
if(temp->right)
enquee(q1,temp->right);
}
if(le==level)
break;
c=0;
}
if(!isEmpty(q1))
{
while(!isEmpty(q1))
{
temp=Dequee(q1);
if(min>temp->info)
min=temp->info;
}
}
else
{
while(!isEmpty(q2))
{
temp=Dequee(q2);
if(min>temp->info)
min=temp->info;
}
}

printf("%d",min);
}

Depth first search will do too, I suppose. (root is at depth 0, children of root at depth 1 etc). Makes it easier to write quicker code because of recursive implementation.

FindMinAtDepth(Tree *t, int depth) {
    return FindMinAtDepthInternal(t, depth, MAX_INT);
}
  
FindMinAtDepthInternal(Tree *t, int depth, int cur_min) {
   
    if (!t) return cur_min;
    // Found at node at require depth. Compare with min seen so far and 
    // return the right value
    if (depth == 0) return t->value < cur_min ? t->value : cur_min;
    
    // Need to go deeper.
    int left_min = FindMinAtDepthInternal(t->left, depth-1, cur_min);
    return FindMinAtDepthInternal(t->right, depth-1, left_min);
}

public static Node findMinByLevel(Node n, int level){
        if(n==null || level==0){
            return n;
        }
        Node left = findMinByLevel(n.left, level-1);
        Node right = findMinByLevel(n.right, level-1);
        if(left==null && right == null){
            return null;
        }
        if(left==null && right != null){
            return right;
        }
        if(left!=null && right == null){
            return left;
        }
        
        if(left.value<right.value)
            return left;
        else
            return right;
    }

1. Connect Siblings of tree till level 'depth'.
2. iterate through the siblings at level 'depth' to find the minimum element

tree* FindMin(tree *t, int h, int *min)
{
if(t == NULL) return NULL;

tree *t1, *t2;
if(h == 0)
{
return t;
}

t1 = FindMin(t->left, h-1);
t2 = FindMin(t->right, h-1);
if(t1 != NULL && t2 != NULL)
{
if(t1 -> val < t2 -> val)
return t1;
return t2;
}
else if(t1 == NULL && t2 != NULL)
return t2;
return t1;
}

Since the question asks about the minimum value at a given node, we can use bfs as many have already mentioned. So, we just need to find out the left most value/node in hte list of nodes at that particualr level. That should do it. All in all, it would be O(n).


Correct me if im wrong.