Univalued Binary Tree solution in Python

Explore More Solutions

Code Solution


class Solution:
    def isUnivalTree(self, root: TreeNode | None) -> bool:
        if not root:
            return True
        if root.left and root.left.val != root.val:
            return False
        if root.right and root.right.val != root.val:
            return False
        return self.isUnivalTree(root.left) and self.isUnivalTree(root.right)

Problem Description

So, you think your family is a bit too much to handle? Imagine a tree where every single node is just like your overly enthusiastic uncle who insists on wearing the same Hawaiian shirt to every family gathering. Welcome to the world of Univalued Binary Trees!

In this LeetCode problem, you are tasked with determining whether a given binary tree is a univalued tree. A univalued tree is one where all nodes have the same value. Think of it as a family reunion where everyone is wearing the same shirt—no one stands out, and you can’t tell who’s who!

Approach

The approach to solving this problem is straightforward. We will traverse the tree recursively and check if each node’s value matches its parent’s value. If we find any node that doesn’t match, we can confidently declare that this tree is not a univalued tree. If we reach the end of our traversal without finding any discrepancies, we can celebrate our univalued family tree!

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n), where n is the number of nodes in the tree.
Space Complexity	O(h), where h is the height of the tree.

Real-World Example

Imagine you walk into a room full of people, and they all have the same name tag. You might think, “Wow, this is a univalued gathering!” If even one person had a different name tag, it would throw off the whole vibe. Similarly, in a univalued binary tree, if even one node has a different value, the whole tree fails to meet the criteria.