scyle
BAN USERThe problem states that all the nodes in the sub-tree should be within the specified range. So we can't just do a simple traversal and count every node within the range.
We count the nodes that are within range for the left tree and then the right tree.
The catch is that if we find any invalid nodes within the tree, then the results returned by the function will be zero.
We can use the BST property (left <= current < right) to help save some time.
I am maintaining the results outside the function which is bad but it can be fixed by having a private Result class.
int maxcount = 0;
Node rootedat = null;
public int countRange(Node node, int x, int y, int min, int max) {
if( x > max || y < min || node == null ) return 0;
int lCount = countRange( node.lChild, x, y, min, node.data);
int rCount = countRange( node.rChild, x, y, node.data+1, max);
// if the left or right subtree are not null, they should return a non-zero number of
// nodes if all the nodes match the criteria. If return is zero, something is out of range.
if( node.lChild != null && lCount == 0 || node.rChild != null && rCount == 0 ) return 0;
int count = 0;
if( x <= node.data && node.data <= y) {
count = lCount + rCount + 1;
if( count > maxcount ) {
maxcount = count;
rootedat = node;
}
}
return count;
}
RepI'm from India, 26 years old. I want to travel, I want a job where I can earn money ...
Using dynamic programming with recursion.
- scyle June 20, 2015