If you’re walking the tree from the root down, you don’t need to propagate ‘counts’ downward at all–the fact that you are is resulting in repeated counting of nodes as they contribute to both count
, countLeft
, and countRight
, since you increment count
before passing it to nodesGreaterThanX
for the children.
public static int nodesGreaterThanX(BinaryTreeNode<Integer> node, int k) {
if (node == null) {
return 0;
}
int countLeft = nodesGreaterThanX(node.left, k);
int countRight = nodesGreaterThanX(node.right, k);
return (node.data > k ? 1 : 0) + countLeft + countRight;
}