Count Value Occurrences in a Binary Tree

Problem Overview

You are given the root of a binary tree (not a BST, just a generic binary tree) and a target value x. Count how many nodes in the tree have node.val == x.

Part 1: Recursive Approach

Implement a recursive function to count the occurrences of the target value x in the binary tree.

Part 2: Iterative Approach

Implement an iterative function to count the occurrences of the target value x in the binary tree.

Constraints

• The number of nodes in the binary tree is between 0 and 10^4.
• Each node's value is an integer between 0 and 10^9.

Examples

Example 1

Input:

• Binary Tree: 1 / \ 2 3 / \ 4 5
• Target value x = 3

Output:

• 1 (There is one node with value 3).

Example 2

Input:

• Binary Tree: 1 / \ 2 3 / \ 4 5
• Target value x = 1

Output:

• 1 (There is one node with value 1).

Example 3

Input:

• Binary Tree: 1 / \ 2 3 / \ 4 5
• Target value x = 4

Output:

• 1 (There is one node with value 4).

Solution

Recursive Approach

`python class TreeNode: def init(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right

def countValueRecur(root, x): if not root: return 0 return (root.val == x) + countValueRecur(root.left, x) + countValueRecur(root.right, x) `

Iterative Approach

`python from collections import deque

def countValueIter(root, x): if not root: return 0 queue = deque([root]) count = 0 while queue: node = queue.popleft() if node.val == x: count += 1 if node.left: queue.append(node.left) if node.right: queue.append(node.right) return count `

Search Results

• DarkInterview URL: Link
• GitHub: Binary Tree Count Value Occurrences
• LeetCode: Count Nodes Equal to Sum of Descendants

Additional Resources

• GeeksforGeeks: Count nodes having value equal to sum of its descendants
• Interview Prep Site: Binary Tree Traversal Techniques