ayanvit
BAN USERPerform a simple depth first traversal of the tree (Pre-order traversal).
Keep a global sum variable and increment it when u move down the tree and decrement when u move up.
Here's the pseudocode :-
int gsum = 0;
int globalsum = 10000; //global sum variable used to store sum
smallestsum(node *root)
{
gsum += root->data;
if(root->left==NULL && root->right==NULL)// on encountering a leaf node
{
if(globalsum > gsum)
globalsum = gsum;
gsum -= root->data;
}
smallestsum(root->left);
smallestsum(root->right);
}
cout<<globalsum;
Perform a simple depth first traversal of the tree (Pre-order traversal).
Keep a global sum variable and increment it when u move down the tree and decrement when u move up.
Here's the pseudocode :-
int gsum = 0;
int globalsum = 10000; //global sum variable used to store sum
smallestsum(node *root)
{
gsum += root->data;
if(root->left==NULL && root->right==NULL)// on encountering a leaf node
{
if(globalsum > gsum)
globalsum = gsum;
gsum -= root->data;
}
smallestsum(root->left);
smallestsum(root->right);
}
cout<<globalsum;
Use In order traversal of the tree.
for ex : if the tree contains 10 nodes, then finding the 2nd largest implies finding the (10-2)th i.e 8th smallest.
Do a simple inorder traversal and get the 8th node. That would be the answer.
Please let me know in case of any concerns.
Thats perfect !!!
- ayanvit November 16, 2011