VMWare Inc Interview Question
Member Technical StaffsCountry: India
Interview Type: In-Person
Do any tree traversal(inorder or preorder or postorder) and keep updating max element
rough algo
void maxelementoftree(struct node* root,int* countref)
{
if(root == NULL)
return;
else
{
maxelementoftree(root->left , countref);
if(root->data > *countref)
*countref = root->data;
maxelementoftree(root->right, countref);
}
}
typedef struct tree {
int val,
struct tree *left;
struct tree *right;
} tree_t;
tree_t * FindLargest(tree_t* node) {
if (NULL == node)
return NULL;
tree_t * left_largest = FindLargest(node->left);
tree_t * right_largest = FindLargest(node->right);
if (NULL == left_largest && NULL == right_largest)
return node;
if (NULL != left_largest && NULL ! = right_largest) {
if ((node->val > right_largest->val) && (node->val > left_largest->val))
return node;
else if (right_largest->val > node->val) && (right_largest->val > left_largest->val))
return right_largest;
else
return left_largest;
}
if (left->largest == NULL)
return (node->val > right_largest->val ? node : right_largest);
else
return (node->val > left_largest->val ? node : right_largest);
}
Basically I'm trying to compare the values of the parent , its left child and right child.
1) If no child is parent , the largets value is of its parent.
2)if both the children are present , return the largest value among the parent and the children
3)If either of the children is present , do the same as case 2
So from each subtree I'm getting the highest value recursively
typedef struct node{
int data;
struct node* left;
struct node* right;
}tree_node;
int max(int a, int b, int c)
{
int m = a;
(m < b) && (m = b); //these are not conditional statements.
(m < c) && (m = c); //these are just boolean expressions.
return m;
}
int max_element(tree_node* root){
if(root == NULL)
return;
if(root->left == NULL && root->right == NULL){
//Hit leaf
return root->data;
}
return max(root->data, max_element(root->left),max_element(root->right));
}
traverse the tree in Inorder form so that you will get the node value in ascending order. Hence the last node value will be the highest value for the binary tree..
Let's assume the tree we're given is defined as follows:
class BinaryTree
{
BinaryTree left, right;
int value;
}
Then, we can accomplish the task with a very simple recursive method. We take the max of the root and the overall max from each of the subtrees, and return the largest of those 3 values. When a node is NULL, we return Integer.MIN_VALUE so it will effectively be ignored in the calculation of the max (since it cannot be greater than any other value that is included in the max calculation, it will have no effect on the outcome). We assume here that the top-level root passed into the method is not null (since if it is, there's no well-defined answer).
public static int maxVal (BinaryTree root)
{
if (root == null) { return Integer.MIN_VALUE; }
int maxSoFar = Math.max(maxVal (root.left), maxVal(root.right));
return Math.max (maxSoFar, root.val);
}
- Anonymous May 06, 2013