imran.sk
BAN USER
Comments (2)
Reputation -5
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
Assuming the tree node structure is not allowed to change,
we can maintain a hash table with bst-tree-node counts for each BST node. We can use preorder traversal to solve this.
{{{
global_max_node_cnt =0;
global_max_sub_tree_root = null;
inorder(Tree *root) {
if(root == null)
return;
if(root->left == null && root->right ==null)
put(root, 1);
inorder(root->left);
visit(root);
inorder(root->right);
if(root->left->key < root->key < root->right->key) {
left_bst_cnt = get(root->left);
right_bst_cnt = get(root->right);
if(left_bst_cnt > 0 && right_bst_cnt > 0) {
put(root, left_bst_cnt + right_bst_cnt + 1);
}
else {
put(root, 0);
}
else {
put(root, 0);
}
if(global_max_node_cnt < get(root)) {
global_max_node_cnt = get(root);
global_max_sub_tree_root = root;
}
}
-
imran.sk
December 07, 2009 | Flag
Reply
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
How to do this when the arrays are relatively huge? Suppose array A is in a disk and array B is in another disk. How do we find out A intersection B efficiently?
- imran.sk April 22, 2012