Flipkart Interview Question
Software Engineer / Developersif its a BST, then we can move to the rightmost element and find the max value...otherwise i guess it takes O(n) complexity to find the max value in a binary tree(simply traverse the entire tree and find the max value)
This is the code I had written
node *max=root; //make it global;
findmax(root);
printf("Maximum val:%d",max->value);
void findmax(node *cur)
{
if(cur->val>max->val)
max=cur;
findmax(cur->left);
findmax(cur->right);
}
How about if we kept a seperate list which contains the max values. before you add or remove an element from the tree compare it to the first element on the list.
public static int findMax(Node start){
if(start == null)
return 0 ;
if(start.left == null && start.right == null)
return start.value;
if(start.left == null)
return Max(start.value , findMax(start.right));
if(start.right == null)
return Max(start.value , findMax(start.left));
return Max(start.value , Max(findMax(start.left), findMax(start.right)));
}
static int Max(int val1 , int val2){
if(val1 > val2)
return val1 ;
return val2;
}
- Anonymous December 05, 2009