Jobs

Interviews

Discussions

Count Univalue Subtrees

#429 Most AskedMedium

Count Univalue Subtrees #429 Most Asked

Medium

Google

13 views

Topics:

TreesRecursion

Given the root of a binary tree, return the number of univalue subtrees.

A univalue 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].
Each node's value will be an integer in the range [0, 99].

Try coding it in LeetCode

Count Univalue Subtrees

#429 Most AskedMedium

Count Univalue Subtrees #429 Most Asked

Medium

Google

13 views

Topics:

TreesRecursion

Given the root of a binary tree, return the number of univalue subtrees.

A univalue 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].
Each node's value will be an integer in the range [0, 99].

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values that the nodes in the tree can hold? Are they integers, and can they be negative?
Can the tree be empty (null)? If so, what should I return?
What constitutes a 'univalue subtree'? Specifically, does a single leaf node qualify as a univalue subtree?
If a node has a value different from its children, but its children are both univalue subtrees with the *same* value as the parent, is the subtree rooted at that node considered a univalue subtree?
Are we dealing with a binary tree, or a more general tree structure?

Brute Force Solution

Approach

The brute force approach to counting univalue subtrees means we will check every single subtree to see if it qualifies. We will look at each node in the tree and consider it as the root of a potential univalue subtree.

Here's how the algorithm would work step-by-step:

For every node in the tree, treat that node as the potential root of a subtree.
Check if the subtree rooted at that node is a univalue subtree. This means checking if every node in that subtree has the same value.
To check if it's a univalue subtree, start at the root and compare its value to the values of its children. If a child's value is different, it's not a univalue subtree. If a child does not exist, skip the comparision.
If the current node and its immediate children have the same value, repeat this process for the children, recursively checking their children until all nodes in this subtree have been verified or a mismatch is found.
If we find that all nodes in the subtree have the same value, increment a counter.
After checking every node in the tree as a potential subtree root, the final count will be the total number of univalue subtrees.

Code Implementation

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def count_univalue_subtrees(root):
    univalue_subtree_count = 0

    def is_univalue_subtree(root_node):
        # If the node is None, it's a univalue subtree by definition
        if root_node is None:
            return True

        # Recursively check if left and right subtrees are univalue
        left_subtree_is_univalue = is_univalue_subtree(root_node.left)
        right_subtree_is_univalue = is_univalue_subtree(root_node.right)

        # If either subtree is not univalue, the entire subtree isn't
        if not left_subtree_is_univalue or not right_subtree_is_univalue:
            return False

        # Check if the current node's value matches its children's values
        if root_node.left and root_node.value != root_node.left.value:
            return False

        if root_node.right and root_node.value != root_node.right.value:
            return False

        return True

    def traverse(root_node):
        nonlocal univalue_subtree_count

        if root_node is None:
            return

        # Check if the subtree rooted at the current node is univalue
        if is_univalue_subtree(root_node):
            # Increment the count if it's a univalue subtree
            univalue_subtree_count += 1

        # Recursively traverse the left and right subtrees
        traverse(root_node.left)
        traverse(root_node.right)

    traverse(root)
    return univalue_subtree_count

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n nodes in the tree, treating each as a potential root of a univalue subtree. For each of these n nodes, the isUnivalueSubtree function potentially visits all nodes within that subtree to verify if it is indeed a univalue subtree. In the worst-case scenario, where the entire tree is skewed, the isUnivalueSubtree function might need to traverse all n nodes for each of the n potential roots. This results in roughly n * n operations, which simplifies to a time complexity of O(n²).

Space Complexity

O(H) – The algorithm uses recursion to traverse the tree. In the worst-case scenario, the recursion stack's depth can be equal to the height of the tree, H. Therefore, the space used by the call stack is proportional to the tree's height. In a skewed tree, H can be equal to N (the number of nodes), but in a balanced tree, H would be log N. Thus, the auxiliary space complexity is O(H), where H is the height of the tree.

Optimal Solution

Approach

The most efficient way to count univalue subtrees is to work from the bottom up. For each node, we check if the subtree rooted at that node is univalue based on its children's properties. We use the results of the smaller subtrees to determine the larger subtrees, thus avoiding redundant calculations.

Here's how the algorithm would work step-by-step:

Start by looking at the smallest parts of the tree – the leaves. Each leaf is automatically a univalue subtree because it has no children.
Move up the tree, one level at a time. For each node, check two things: first, if the node's value is the same as its children's values. Second, if its children are *themselves* roots of univalue subtrees.
If both of those things are true, then the subtree rooted at the current node is also a univalue subtree. Count it!
If either of those things is false, the subtree is *not* univalue. Don't count it!
Keep going up the tree, repeating this process for each node. The 'univalue-ness' of smaller subtrees helps you decide about larger ones.
When you reach the very top (the root of the whole tree), you will have considered every subtree and counted exactly the ones that are univalue.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def count_univalue_subtrees(root):
    number_of_univalue_subtrees = 0

    def is_univalue(node):
        nonlocal number_of_univalue_subtrees

        if not node:
            return True

        # Check univalueness of subtrees first.
        is_left_univalue = is_univalue(node.left)
        is_right_univalue = is_univalue(node.right)

        if not is_left_univalue or not is_right_univalue:
            return False

        # If children exist, check if their values match the current node.
        if node.left and node.left.val != node.val:
            return False

        if node.right and node.right.val != node.val:
            return False

        # If all checks pass, increment the counter.
        number_of_univalue_subtrees += 1

        return True

    is_univalue(root)
    return number_of_univalue_subtrees

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each node in the tree exactly once. For each node, it performs a constant amount of work: comparing the node's value with its children's values and checking if the subtrees rooted at its children are univalue. Since the amount of work per node is constant and we visit each of the n nodes once, the overall time complexity is O(n).

Space Complexity

O(H) – The algorithm uses a recursive approach, and the space complexity is determined by the depth of the recursion stack. In the worst-case scenario, the tree is skewed, and the recursion depth is equal to the height (H) of the tree. Therefore, the maximum space used by the call stack is proportional to the tree's height. In the average case for a balanced tree, H would be log N. However, in the worst case, H can be equal to N. So, the auxiliary space is O(H).

Edge Cases

Case	How to Handle
Null or empty tree	Return 0, as an empty tree has no subtrees (univalue or otherwise).
Single node tree	Return 1, as a single node is a univalue subtree by definition.
Tree with all identical values	The entire tree is a single univalue subtree, and every node within it is also a univalue subtree.
Highly skewed tree (e.g., all nodes on one side)	The recursive calls will correctly traverse the skewed tree to identify all univalue subtrees even if it may lead to higher call stack depth.
Tree with alternating values at each level	Each node will have a value different from its children preventing any subtree bigger than a single node from being univalue.
Tree with Integer.MAX_VALUE or Integer.MIN_VALUE as node values	Comparisons between node values and child values should still work correctly.
Large tree (potential stack overflow with recursion)	Consider using iterative approach with explicit stack for very large trees, to avoid stack overflow.
Tree with duplicate subtrees, some univalue, some not	The recursive algorithm correctly explores each subtree and determines univalue status independently, correctly counting only univalue ones.

Null or empty tree

How to Handle:

Return 0, as an empty tree has no subtrees (univalue or otherwise).

Single node tree

How to Handle:

Return 1, as a single node is a univalue subtree by definition.

Tree with all identical values

How to Handle:

The entire tree is a single univalue subtree, and every node within it is also a univalue subtree.

Highly skewed tree (e.g., all nodes on one side)

How to Handle:

The recursive calls will correctly traverse the skewed tree to identify all univalue subtrees even if it may lead to higher call stack depth.

Tree with alternating values at each level

How to Handle:

Each node will have a value different from its children preventing any subtree bigger than a single node from being univalue.

Tree with Integer.MAX_VALUE or Integer.MIN_VALUE as node values

How to Handle:

Comparisons between node values and child values should still work correctly.

Large tree (potential stack overflow with recursion)

How to Handle:

Consider using iterative approach with explicit stack for very large trees, to avoid stack overflow.

Tree with duplicate subtrees, some univalue, some not

How to Handle:

The recursive algorithm correctly explores each subtree and determines univalue status independently, correctly counting only univalue ones.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values that the nodes in the tree can hold? Are they integers, and can they be negative?
Can the tree be empty (null)? If so, what should I return?
What constitutes a 'univalue subtree'? Specifically, does a single leaf node qualify as a univalue subtree?
If a node has a value different from its children, but its children are both univalue subtrees with the *same* value as the parent, is the subtree rooted at that node considered a univalue subtree?
Are we dealing with a binary tree, or a more general tree structure?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

For every node in the tree, treat that node as the potential root of a subtree.
Check if the subtree rooted at that node is a univalue subtree. This means checking if every node in that subtree has the same value.
To check if it's a univalue subtree, start at the root and compare its value to the values of its children. If a child's value is different, it's not a univalue subtree. If a child does not exist, skip the comparision.
If the current node and its immediate children have the same value, repeat this process for the children, recursively checking their children until all nodes in this subtree have been verified or a mismatch is found.
If we find that all nodes in the subtree have the same value, increment a counter.
After checking every node in the tree as a potential subtree root, the final count will be the total number of univalue subtrees.

Code Implementation

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def count_univalue_subtrees(root):
    univalue_subtree_count = 0

    def is_univalue_subtree(root_node):
        # If the node is None, it's a univalue subtree by definition
        if root_node is None:
            return True

        # Recursively check if left and right subtrees are univalue
        left_subtree_is_univalue = is_univalue_subtree(root_node.left)
        right_subtree_is_univalue = is_univalue_subtree(root_node.right)

        # If either subtree is not univalue, the entire subtree isn't
        if not left_subtree_is_univalue or not right_subtree_is_univalue:
            return False

        # Check if the current node's value matches its children's values
        if root_node.left and root_node.value != root_node.left.value:
            return False

        if root_node.right and root_node.value != root_node.right.value:
            return False

        return True

    def traverse(root_node):
        nonlocal univalue_subtree_count

        if root_node is None:
            return

        # Check if the subtree rooted at the current node is univalue
        if is_univalue_subtree(root_node):
            # Increment the count if it's a univalue subtree
            univalue_subtree_count += 1

        # Recursively traverse the left and right subtrees
        traverse(root_node.left)
        traverse(root_node.right)

    traverse(root)
    return univalue_subtree_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the smallest parts of the tree – the leaves. Each leaf is automatically a univalue subtree because it has no children.
Move up the tree, one level at a time. For each node, check two things: first, if the node's value is the same as its children's values. Second, if its children are *themselves* roots of univalue subtrees.
If both of those things are true, then the subtree rooted at the current node is also a univalue subtree. Count it!
If either of those things is false, the subtree is *not* univalue. Don't count it!
Keep going up the tree, repeating this process for each node. The 'univalue-ness' of smaller subtrees helps you decide about larger ones.
When you reach the very top (the root of the whole tree), you will have considered every subtree and counted exactly the ones that are univalue.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def count_univalue_subtrees(root):
    number_of_univalue_subtrees = 0

    def is_univalue(node):
        nonlocal number_of_univalue_subtrees

        if not node:
            return True

        # Check univalueness of subtrees first.
        is_left_univalue = is_univalue(node.left)
        is_right_univalue = is_univalue(node.right)

        if not is_left_univalue or not is_right_univalue:
            return False

        # If children exist, check if their values match the current node.
        if node.left and node.left.val != node.val:
            return False

        if node.right and node.right.val != node.val:
            return False

        # If all checks pass, increment the counter.
        number_of_univalue_subtrees += 1

        return True

    is_univalue(root)
    return number_of_univalue_subtrees

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty tree	Return 0, as an empty tree has no subtrees (univalue or otherwise).
Single node tree	Return 1, as a single node is a univalue subtree by definition.
Tree with all identical values	The entire tree is a single univalue subtree, and every node within it is also a univalue subtree.
Highly skewed tree (e.g., all nodes on one side)	The recursive calls will correctly traverse the skewed tree to identify all univalue subtrees even if it may lead to higher call stack depth.
Tree with alternating values at each level	Each node will have a value different from its children preventing any subtree bigger than a single node from being univalue.
Tree with Integer.MAX_VALUE or Integer.MIN_VALUE as node values	Comparisons between node values and child values should still work correctly.
Large tree (potential stack overflow with recursion)	Consider using iterative approach with explicit stack for very large trees, to avoid stack overflow.
Tree with duplicate subtrees, some univalue, some not	The recursive algorithm correctly explores each subtree and determines univalue status independently, correctly counting only univalue ones.

Null or empty tree

How to Handle:

Return 0, as an empty tree has no subtrees (univalue or otherwise).

Single node tree

How to Handle:

Return 1, as a single node is a univalue subtree by definition.

Tree with all identical values

How to Handle:

The entire tree is a single univalue subtree, and every node within it is also a univalue subtree.

Highly skewed tree (e.g., all nodes on one side)

How to Handle:

The recursive calls will correctly traverse the skewed tree to identify all univalue subtrees even if it may lead to higher call stack depth.

Tree with alternating values at each level

How to Handle:

Each node will have a value different from its children preventing any subtree bigger than a single node from being univalue.

Tree with Integer.MAX_VALUE or Integer.MIN_VALUE as node values

How to Handle:

Comparisons between node values and child values should still work correctly.

Large tree (potential stack overflow with recursion)

How to Handle:

Consider using iterative approach with explicit stack for very large trees, to avoid stack overflow.

Tree with duplicate subtrees, some univalue, some not

How to Handle:

The recursive algorithm correctly explores each subtree and determines univalue status independently, correctly counting only univalue ones.

0/1916 Google questions completed

0/1916 completed