We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Univalued Binary Tree

Number: 1005

Difficulty: Easy

Paid? No

Companies: Twilio

Problem Description

A binary tree is uni-valued if every node in the tree has the same value. Given the root of a binary tree, return true if the entire tree has the same value, or false otherwise.

Key Insights

  • The goal is to verify that all nodes in the tree share the same value.
  • Traverse the tree (using DFS or BFS) and compare each node’s value with the root's value.
  • If any node differs, the tree is not uni-valued.
  • A recursive depth-first search (DFS) can be used efficiently given the tree's small size (up to 100 nodes).

Space and Time 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 (recursive stack space).

Solution

We start by recording the root node's value, then perform a depth-first search (DFS) traversal. At each node, we check if its value matches the root's value. If a mismatch is found, we immediately return false. If all nodes pass the check, the function returns true. This approach leverages recursion and is both simple and efficient for the problem's constraints.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Function to check if the tree is uni-valued
def isUnivalTree(root: TreeNode) -> bool:
    target_value = root.val  # store the root's value for comparison

    def dfs(node: TreeNode) -> bool:
        if node is None:  # base case: node is null
            return True
        if node.val != target_value:  # if current node's value differs, return False
            return False
        # recursively check left and right subtrees
        return dfs(node.left) and dfs(node.right)

    return dfs(root)
← Back to All Questions