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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Univalued Binary Tree

Difficulty: Easy

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 given tree is uni-valued, or false otherwise.

Key Insights

  • A uni-valued binary tree contains nodes with the same value across all its nodes.
  • The tree can be traversed using Depth-First Search (DFS) or Breadth-First Search (BFS) to check the values of the nodes.
  • The problem can be solved recursively or iteratively.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the binary tree, as we may need to visit each node once. Space Complexity: O(h), where h is the height of the tree, due to the recursion stack in the case of DFS or the queue in the case of BFS.

Solution

To determine if the binary tree is uni-valued, we can use either a recursive approach or an iterative approach. We'll traverse the tree and check if all nodes have the same value as the root node's value. We can use a stack or queue for DFS or BFS, respectively.

Code Solutions

def isUnivalTree(root):
    if not root:
        return True
    def dfs(node, value):
        if not node:
            return True
        if node.val != value:
            return False
        return dfs(node.left, value) and dfs(node.right, value)
    
    return dfs(root, root.val)
← Back to All Questions