Count Univalue Subtrees - Practice Coding Problems

Count Univalue Subtrees - Problem

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:

Input: root = [5,1,5,5,5,null,5]
Output: 4
Explanation: There are 4 uni-value subtrees

Input & Output

Example 1 — Mixed Tree with 4 Uni-value Subtrees

$ Input: root = [5,1,5,5,5,null,5]

› Output: 4

💡 Note: The four uni-value subtrees are: three leaf nodes with value 5, and the right subtree rooted at 5 (which contains only node 5). The subtree rooted at node 1 is not uni-value because it contains both 1 and 5.

Example 2 — Single Node

$ Input: root = [1]

› Output: 1

💡 Note: A single node is always a uni-value subtree by itself.

Example 3 — All Same Values

$ Input: root = [5,5,5,5,5,5,5]

› Output: 7

💡 Note: All nodes have the same value, so every subtree is uni-value. Total 7 nodes = 7 uni-value subtrees.

Constraints

The number of nodes in the tree is in the range [1, 1000]
-1000 ≤ Node.val ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree [5,1,5,5,5,null,5] with mixed values

Identify Uniform

Find subtrees where all nodes have same value

Count Result

Total count of uni-value subtrees is 4

Key Takeaway

🎯 Key Insight: Use post-order traversal to check uniformity bottom-up efficiently

Asked in

G Google 15 f Facebook 12

The key insight is to use post-order DFS traversal to check uniformity bottom-up. A subtree is uniform only if both children are uniform and have the same value as the parent. Best approach is DFS Post-Order with Time: O(n), Space: O(h).

Common Approaches

Approach	Time	Space	Notes
✓ DFS Post-Order Traversal	O(n)	O(h)	Single traversal using post-order DFS to check uniformity and count simultaneously
Brute Force - Check Every Subtree	O(n²)	O(h)	For each node, recursively check if its entire subtree has uniform values

DFS Post-Order Traversal — Algorithm Steps

Step 1: Visit left and right children first
Step 2: Check if current subtree is uniform
Step 3: Count and return uniformity status

Visualization

Tap to expand

Step-by-Step Walkthrough

Post-Order

Visit left child, right child, then current node

Check Uniformity

Current subtree uniform if both children uniform and same value

Count & Return

Count uniform subtrees and return status up the tree

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct Result {
    bool uniform;
    int count;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

struct Result dfs(struct TreeNode* node) {
    struct Result result;
    if (!node) {
        result.uniform = true;
        result.count = 0;
        return result;
    }
    
    struct Result left = dfs(node->left);
    struct Result right = dfs(node->right);
    
    bool currentUniform = true;
    
    if (node->left && (!left.uniform || node->left->val != node->val)) {
        currentUniform = false;
    }
    if (node->right && (!right.uniform || node->right->val != node->val)) {
        currentUniform = false;
    }
    
    int count = left.count + right.count;
    if (currentUniform) {
        count++;
    }
    
    result.uniform = currentUniform;
    result.count = count;
    return result;
}

int solution(struct TreeNode* root) {
    if (!root) return 0;
    return dfs(root).count;
}

int main() {
    struct TreeNode* root = createNode(5);
    root->left = createNode(1);
    root->right = createNode(5);
    root->left->left = createNode(5);
    root->left->right = createNode(5);
    root->right->right = createNode(5);
    
    printf("%d\n", solution(root));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once in post-order traversal

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h

✓ Linear Space

28.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS Post-Order Traversal — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler