704986. BBT counter
Easy
BBT Counter
Slug: bbt-counter4914
Difficulty: Easy
Id: 704986
Topic Tags: Mathematical, Tree, Data Structures, Algorithms
Company Tags: None
Summary
The BBT counter problem involves counting the number of times a given value appears in a binary tree. The problem requires an understanding of basic tree traversal algorithms and mathematical concepts.
Detailed Explanation
To solve this problem, we will use a depth-first search (DFS) approach to traverse the binary tree and count the occurrences of the target value.
Here's a step-by-step breakdown of the solution:
- Define a recursive function
countBBTthat takes the root node of the binary tree and the target value as input. - Initialize a variable
countto zero, which will store the number of times the target value appears in the tree. - If the current node is null, return immediately (base case for recursion).
- Recursively call
countBBTon the left subtree (if it exists) and increment the count by one if the target value is found. - Recursively call
countBBTon the right subtree (if it exists) and increment the count by one if the target value is found. - Return the total count.
Time complexity: O(n), where n is the number of nodes in the tree. Space complexity: O(h), where h is the height of the tree, due to recursive function calls.
Optimized Solutions
Java
public int countBBT(Node root, int target) {
if (root == null) return 0;
int count = 0;
count += countBBT(root.left, target);
if (root.val == target) count++;
count += countBBT(root.right, target);
return count;
}
class Node {
int val;
Node left, right;
}