scofield
BAN USERDiameter is the maximum distance from one leaf node to another.
It is the maximum path length which can either pass through root of the subtree at that point or may not , as it may entirely lie in the left/right subpart of the tree. So basically it is the maximum of left-diamter, right-diameter and the height of the tree(case when diameter passes through the current root).
diamter = max(height ,max (leftDiameter , rightDiamter) )
pass the parameter of height to avoid extra calls during recursion and then update the current height. Return the maximum of diamter from that node.
int diameter(node * root, int *height){
if(root == NULL) { height = 0; return 0;}
int leftHeight =0 , rightHeight = 0;
int leftDiamter = diameter(root->left , &lh);
int rightDiameter = diameter(root->right, &rh);
*height = max(leftHeight, rightHeight) + 1 ;
return max( (max ( leftDiamter , rightDiameter ) , height );
}
Time Complexity = O(n) // as only 1 visit to all the nodes.
- scofield April 05, 2012
Assuming that the number of digits are even. Though the algo can be changed to odd digit too..(only year can make it an odd digit if it is less than 1000. say 976-12-11 is an odd digit)
ALGO:-
First choose the pivot elements. In an even digit number there are 2 pivots.
Next increment the Pivot Elements by 1 . So now the date becomes
Next again increment it.
Next we check all this until 9 . Which again leads to not a valid date.
Now we move to the next pivot element
Now again be do the same. But we also replace the in between digits by the least number .
i.e 0
So the next valid date comes as
This is a valid date, And hence the Next Palindrome Date.
- scofield April 30, 2012-------RETURN ------