Return how many nodes in the tree hold a given target value.
treeValueCount(root, target)
Input format: tree | target.
(1 4 4 x x 4 1), 4 // → 3
(1 2 3), 9 // → 0
(empty), 0 // → 0
This is a counting variant of the same recursive shape as "count all nodes" or "sum all values": instead of every node contributing automatically, each contributes conditionally — 1 if it matches the target, 0 otherwise.
For any node: how many matches live in the subtree rooted here? That's this node's own contribution (0 or 1) plus matches in the left subtree plus matches in the right — every node in the subtree is one of those three places, no overlap, no gaps.
An empty subtree has zero matches — the same neutral base case as counting or summing.
A plain existence check can stop the moment it finds one match. Here, finding one match doesn't tell you whether others exist elsewhere — the target could appear multiple times, so you can't short-circuit. Every node genuinely has to be checked.
Like tree-min-value, this works regardless of any ordering rules, since a value match has nothing to do with ordering. Structurally, it's the same problem as tree-sum with a different per-node rule: "add 1 if I match, else 0" instead of "add my own value." A whole family of tree problems — count, sum, count-matches, find max/min — share this identical skeleton, only the per-node rule changes.
Every node must be visited once, so work is proportional to the number of nodes, with recursion memory bounded by the tree's height.
def tree_value_count(root, target):
if root is None:
return 0
count = 1 if root.val == target else 0
return count + tree_value_count(root.left, target) + tree_value_count(root.right, target)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.