Count Univalue Subtrees medium

Problem Statement

Given the root of a binary tree, return the number of uni-value subtrees.

A uni-value subtree means all nodes of the subtree have the same value.

Example 1:

Input: root = [5,1,5,5,5,null,5] Output: 4

Example 2:

Input: root = [] Output: 0

Steps

1. Recursive Approach: We'll use a recursive function countUnivalSubtrees that takes a node as input and returns a pair:

   • A boolean indicating whether the subtree rooted at this node is a uni-value subtree.
   • The count of uni-value subtrees in this subtree.

2. Base Case: If the node is null, return (true, 0). An empty subtree is considered a uni-value subtree (vacuously true).

3. Recursive Calls: Recursively call countUnivalSubtrees on the left and right children.

4. Uni-value Check: A subtree is uni-value if:

   • It's not null.
   • Its left and right subtrees are uni-value.
   • The values of the left and right children (if they exist) are equal to the current node's value.

5. Count Update: If the current subtree is uni-value, increment the count of uni-value subtrees.

Explanation

The algorithm works by recursively checking each subtree. The base case handles empty subtrees. The recursive step checks if a node's children form uni-value subtrees and if their values match the node's value. This ensures that the entire subtree rooted at the current node is uni-value. The count is updated accordingly. The final count represents the total number of uni-value subtrees in the entire tree.

Code

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public int countUnivalSubtrees(TreeNode root) {
        int[] count = new int[1]; // Using an array to modify count in recursive function.
        helper(root, count);
        return count[0];
    }

    private Pair helper(TreeNode node, int[] count) {
        if (node == null) {
            return new Pair(true, 0);
        }

        Pair left = helper(node.left, count);
        Pair right = helper(node.right, count);

        boolean isUnival = true;
        if (!left.isUnival || !right.isUnival) {
            isUnival = false;
        }
        if (node.left != null && node.left.val != node.val) {
            isUnival = false;
        }
        if (node.right != null && node.right.val != node.val) {
            isUnival = false;
        }

        if (isUnival) {
            count[0]++;
        }

        return new Pair(isUnival, left.count + right.count);
    }

    private class Pair {
        boolean isUnival;
        int count;

        Pair(boolean isUnival, int count) {
            this.isUnival = isUnival;
            this.count = count;
        }
    }
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node once.
• Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be equal to N. The Pair objects also contribute to space complexity but linearly with the height.