find the number of nodes in a binary tree greater than x

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;
}

Leave a Comment