Count Univalue Subtrees in C++
In this article, we will discuss the Count Univalue Subtree in C++ and its applications.
What is a Univalue Subtree?
A univalue subtree is a subtree within a binary tree where all nodes have the same value. For example, in the tree below, both the left and right subtrees rooted at node 1 are univalue subtrees:
1
/ \
1 1
/ \ \
1 1 1
Approach to Count Univalue Subtrees:
We can use a recursive approach to count univalue subtrees in a binary tree. Here's the general idea of this approach:
- First, we define a function isUnivalueSubtree(TreeNode* root) that checks if a subtree rooted at a given node is a univalue subtree.
- After that, we define another function, countUnivalueSubtrees(TreeNode* root), which recursively traverses the binary tree counts univalve subtrees and returns the total count.
Step by Step Implementation in C++:
Step 1: Define the TreeNode structurestruct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
Step 2: Implement the isUnivalueSubtree function
int isUnivalueSubtree(TreeNode* root) {
if (root == nullptr) {
return 1; // Empty subtree is considered univalue
}
int leftUnivalue = isUnivalueSubtree(root->left);
int rightUnivalue = isUnivalueSubtree(root->right);
if ((!leftUnivalue || !rightUnivalue) ||
(root->left != nullptr && root->left->val != root->val) ||
(root->right != nullptr && root->right->val != root->val)) {
return 0;
}
return 1; // All conditions met, it's a univalue subtree
}
Step 3: Implement the countUnivalueSubtrees function
int countUnivalueSubtrees(TreeNode* root) {
if (root == nullptr) {
return 0; // Empty tree has no subtrees
}
int isRootUnivalue = isUnivalueSubtree(root);
int leftCount = countUnivalueSubtrees(root->left);
int rightCount = countUnivalueSubtrees(root->right);
return isRootUnivalue + leftCount + rightCount;
}
Complete Implementation:
Let us take a look the implementations of Count Univalue Subtrees in C++.
#include <iostream>
using namespace std;
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// Function to check if a subtree rooted at a given node is a univalue subtree
int isUnivalueSubtree(TreeNode* root) {
if (root == nullptr) {
return 1; // Empty subtree is considered univalue
}
// Check if left and right subtrees are univalue
int leftUnivalue = isUnivalueSubtree(root->left);
int rightUnivalue = isUnivalueSubtree(root->right);
// If not univalue or if root's value doesn't match child subtrees, return 0
if ((!leftUnivalue || !rightUnivalue) ||
(root->left != nullptr && root->left->val != root->val) ||
(root->right != nullptr && root->right->val != root->val)) {
return 0;
}
return 1; // All conditions met, it's a univalue subtree
}
// Function to count the number of univalue subtrees in the given binary tree
int countUnivalueSubtrees(TreeNode* root) {
if (root == nullptr) {
return 0; // Empty tree has no subtrees
}
// Check if the root itself is a univalue subtree
int isRootUnivalue = isUnivalueSubtree(root);
// Recursively count subtrees from left and right children
int leftCount = countUnivalueSubtrees(root->left);
int rightCount = countUnivalueSubtrees(root->right);
// Total count is the sum of root (if univalue), left subtree count, and right subtree count
return isRootUnivalue + leftCount + rightCount;
}
int main() {
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(1);
root->right = new TreeNode(1);
root->left->left = new TreeNode(1);
root->left->right = new TreeNode(1);
root->right->right = new TreeNode(1);
int univalueCount = countUnivalueSubtrees(root);
cout << "Number of univalue subtrees: " << univalueCount << endl;
// Free allocated memory
delete root->left->left;
delete root->left->right;
delete root->right->right;
delete root->left;
delete root->right;
delete root;
return 0;
}
Output:
![Count Univalue Subtrees in C++](https://static.tutorialandexample.com/cpp/count-univalue-subtrees-in-cpp1.png)
Applications of Count Univalue Subtrees:
There are several applications of the Count Univalue Subtrees in C++. Some main applications of the Count Univalue Subtrees are as follows:
Natural Language Processing (NLP): Trees are used in NLP to represent syntactic structures such as parse trees or dependency trees. Identifying univalue subtrees within these linguistic structures can help parse sentences, extract grammatical relationships, and analyze language syntax.
Tree Analysis in Computer Science: Univalue subtrees are often used in tree-related algorithms and data structures. They can help analyze the structure and properties of trees, leading to the development of efficient algorithms for tasks such as traversal, searching, and manipulation.
Bioinformatics: Trees are commonly used to represent evolutionary relationships between species or genes. Identifying univalue subtrees within these evolutionary trees can provide insights into evolutionary patterns, genetic similarities, and species divergence.
Image Processing: In image processing, trees represent hierarchical structures such as image segmentation, object hierarchies, or scene graphs. Univalue subtrees can help identify regions or objects within an image with similar characteristics or properties.
Data Mining and Machine Learning: Trees are fundamental structures in machine learning algorithms, such as decision trees and random forests. Identifying univalue subtrees within these models can help understand the decision-making process and feature importance, leading to improved model interpretability and performance.
Network Analysis: In network analysis, trees are used to model hierarchical structures such as organizational hierarchies, social networks, or computer networks. Univalue subtrees can be utilized to identify cohesive subgroups or communities within these networks, aiding in network visualization, clustering, and community detection.