Skip to main content
Talentd

Count Univalue Subtrees - Solution & Explanation

MediumPremiumFree on FleetCodeTreeDepth-First SearchBinary Tree6 min readAsked at: Amazon, Google, Zeta +1
Practice this problem

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

Example 3:

Input: root = [5,5,5,5,5,null,5]
Output: 6

 

Constraints:

  • The number of the node in the tree will be in the range [0, 1000].
  • -1000 <= Node.val <= 1000

Approach Overview

Problem Overview: Given a binary tree, count how many subtrees are univalue. A subtree is univalue if every node inside it has the same value. Each node can be the root of its own subtree, so you must verify whether all nodes below it match.

Approach 1: Brute Force Subtree Validation (O(n^2) time, O(h) space)

Traverse every node and treat it as the root of a potential univalue subtree. For each node, run a helper DFS that checks whether all nodes in that subtree match the root value. This repeatedly scans the same nodes when validating overlapping subtrees, which leads to O(n^2) time in the worst case for skewed trees. Space complexity is O(h) due to recursion depth, where h is the tree height. This approach is straightforward but inefficient because subtree validation is recomputed many times.

Approach 2: Postorder DFS with State Propagation (O(n) time, O(h) space)

Traverse the tree using postorder DFS so children are processed before their parent. Each recursive call returns whether the current subtree is univalue. A node forms a univalue subtree if its left and right subtrees are univalue and their values (if they exist) match the current node's value. When this condition holds, increment a global counter and return true to the parent. Every node is visited exactly once, giving O(n) time complexity with O(h) recursion stack space. This approach avoids repeated subtree scans by propagating validity information upward.

The algorithm relies on standard traversal patterns from depth-first search applied to a binary tree. Postorder traversal is key because a node's validity depends on the results from both children.

Recommended for interviews: The postorder DFS approach is what interviewers expect. It demonstrates that you can propagate state during recursion and avoid redundant work. Mentioning the brute force method first shows understanding of the problem space, but implementing the O(n) DFS solution proves stronger algorithmic thinking when working with tree structures.

Solution

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subtree ValidationO(n^2)O(h)Conceptual starting point to understand subtree validation logic
Postorder DFS with State PropagationO(n)O(h)Optimal solution for interviews and production tree traversal problems

Video Solution

LEETCODE 250 (JAVASCRIPT) | COUNT UNIVALUE SUBTREES • Andy Gala • 2,572 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count Univalue Subtrees easy or hard?
Count Univalue Subtrees is considered a medium difficulty problem. The challenge comes from recognizing that postorder traversal is required and designing a recursive function that returns subtree validity while counting results efficiently.
Count Univalue Subtrees Python/Java solution
Python and Java solutions typically implement a recursive postorder DFS function that returns whether a subtree is univalue. A shared counter variable tracks how many valid subtrees are found while traversing the tree once in O(n) time.
How to solve Count Univalue Subtrees in O(n)?
Use a postorder DFS traversal. Process the left and right subtrees first, then determine whether the current node forms a univalue subtree by comparing its value with its children. Return a boolean indicating subtree validity and increment a counter whenever a valid univalue subtree is found.
What is the best approach for Count Univalue Subtrees?
The best approach uses postorder depth-first search. Each recursive call determines whether the current subtree is univalue by checking results from the left and right children. If both subtrees are univalue and their values match the current node, increment the counter. This solution runs in O(n) time and O(h) space.
Is Count Univalue Subtrees asked at Google/Amazon/Meta?
Tree DFS problems similar to Count Univalue Subtrees appear in interviews at companies like Amazon, Google, and Meta. Interviewers use these questions to evaluate recursive thinking, tree traversal skills, and the ability to propagate state during DFS.
What data structure is used in Count Univalue Subtrees?
The problem uses a binary tree as the primary data structure. The algorithm relies on depth-first search traversal, typically implemented with recursion and a counter variable to track valid univalue subtrees.
What is the time complexity of Count Univalue Subtrees?
The optimal solution runs in O(n) time because each node in the binary tree is visited exactly once during the DFS traversal. Space complexity is O(h), where h is the height of the tree due to the recursion stack.

Ready to solve this problem?

Practice Count Univalue Subtrees with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Univalue Path

Next

Subtree of Another Tree