Introduction

A unival subtree is a tree where all the nodes have the same value. Counting the number of unival subtrees in a binary tree is a common problem in computer science. This problem can be solved using a recursive approach, which involves traversing the tree and checking each node to see if it is a unival subtree. In this article, we will discuss the algorithm for counting the number of unival subtrees in a binary tree and provide a sample implementation in Java.

Solution

// A unival tree is a tree where all the nodes have the same value.

// Solution:

// We can use a recursive approach to solve this problem. We will traverse the tree and for each node, we will check if the node and all its children are unival. If they are, we will increment a counter.

// The function below takes in a node and returns true if the subtree rooted at that node is unival, and false otherwise.

function isUnival(node) {
// base case – if node is null, then it is unival
if (node == null) {
return true;
}

// if left and right subtrees are unival and node’s value is equal to left and right subtree’s value, then the tree is unival
if (isUnival(node.left) && isUnival(node.right) && node.left.val == node.val && node.right.val == node.val) {
return true;
}

// otherwise, the tree is not unival
return false;
}

// Now, we can use this function to count the number of unival subtrees in a binary tree.

function countUnivalSubtrees(root) {
// base case – if root is null, then there are no unival subtrees
if (root == null) {
return 0;
}

// count the number of unival subtrees in the left and right subtrees
let leftCount = countUnivalSubtrees(root.left);
let rightCount = countUnivalSubtrees(root.right);

// if the root is a unival subtree, then increment the count
if (isUnival(root)) {
return 1 + leftCount + rightCount;
}

// otherwise, just return the count of unival subtrees in the left and right subtrees
return leftCount + rightCount;
}

int countUniVals(node* head, bool* unival) {
    if (!node) {
        *unival = true;
        return 0;
    }
    bool uniL,uniR;
    int sum = countUniVals(head->l, &uniL) + countUniVals(head->r, &uniR);
    if (uniL && uniR &&
        (!head->l || head->l->val == head->val) && 
        (!head->r || head->r->val == head->val)) {
        sum++;
        *unival = true;
    }
    return sum;
}

Counting the Number of Unival Subtrees in a Binary Tree

A unival subtree is a tree where all the nodes have the same value. Counting the number of unival subtrees in a binary tree can be a difficult task. In this article, we will discuss how to count the number of unival subtrees in a binary tree.

What is a Unival Subtree?

A unival subtree is a tree where all the nodes have the same value. This means that all the nodes in the tree have the same data value. For example, if the root node has a value of 5, then all the other nodes in the tree must also have a value of 5.

How to Count the Number of Unival Subtrees in a Binary Tree

The first step in counting the number of unival subtrees in a binary tree is to traverse the tree. This can be done using a depth-first search or a breadth-first search. Once the tree has been traversed, the next step is to check each node to see if it is a unival subtree. If it is, then the number of unival subtrees is incremented. This process is repeated until all the nodes in the tree have been checked.

Once the number of unival subtrees has been counted, the total number of unival subtrees in the tree can be determined. This can be done by adding up the number of unival subtrees in each subtree. For example, if there are three subtrees in the tree, and each subtree has two unival subtrees, then the total number of unival subtrees in the tree is six.

Conclusion

Counting the number of unival subtrees in a binary tree can be a difficult task. However, by using a depth-first search or a breadth-first search to traverse the tree, and then checking each node to see if it is a unival subtree, the total number of unival subtrees in the tree can be determined. This can be done by adding up the number of unival subtrees in each subtree.