algoadvance

Given a binary tree, determine if it is a univalued binary tree, which means all nodes of the tree have the same value.

Example:

Input: [1,1,1,1,1,null,1]
Output: True

Input: [2,2,2,5,2]
Output: False

Clarifying Questions

1. What should be returned if the tree is empty?
   • Return True, as an empty tree can be considered trivially univalued.
2. Are there any constraints on the values within the tree nodes?
   • The problem does not specify constraints on the node values; you can assume they can be any integer.

Strategy

1. Tree Traversal: We can perform a Depth-First Search (DFS) or Breadth-First Search (BFS) on the tree.
2. Comparison: During the traversal, compare every node’s value to the root node’s value.
3. Conclusively Determine: If all nodes have the same value, return True. Otherwise, return False.

We’ll use DFS for simplicity in the implementation.

Time Complexity

• Time Complexity: O(N), where N is the number of nodes in the binary tree. We need to visit each node once to verify its value.
• Space Complexity: O(H), where H is the height of the tree. This is the space required for the function call stack in the case of the recursive DFS implementation.

Code

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

def isUnivalTree(root: TreeNode) -> bool:
    if not root:
        return True
    
    def dfs(node: TreeNode, value: int) -> bool:
        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)

# Example usage:
# Constructing a binary tree [1,1,1,1,1,null,1]

root = TreeNode(1)
root.left = TreeNode(1)
root.right = TreeNode(1)
root.left.left = TreeNode(1)
root.left.right = TreeNode(1)
root.right.right = TreeNode(1)

print(isUnivalTree(root))  # Should return True

root2 = TreeNode(2)
root2.left = TreeNode(2)
root2.right = TreeNode(2)
root2.left.left = TreeNode(5)
root2.left.right = TreeNode(2)

print(isUnivalTree(root2))  # Should return False

Explanation

1. TreeNode Class: Basic definition of the TreeNode.
2. DFS Traversal:
   • Base Case: If the node is None, return True.
   • If the current node’s value does not match the initial value, return False.
   • Recursively check the left and right subtrees.
3. Initial Call: We start the DFS with the root node’s value.

By using this approach, we ensure that all nodes are checked efficiently for the univalued property.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?