Notebook

965. Univalued Binary Tree

A binary tree is univalued if every node in the tree has the same value.

Return true if and only if the given tree is univalued.

Example 1:

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

Example 2:

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

Note:

The number of nodes in the given tree will be in the range [1, 100].
Each node's value will be an integer in the range [0, 99].

Source

In [3]:

# 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

Code

In [4]:

def is_unival_tree(root):
    """Recursive approach (DFS)"""
    def dfs(node, x):
        # base case
        if not node:
            return True
        
        if node.val != x:
            return False
        return dfs(node.left, x) and dfs(node.right, x)

    if root:
        return dfs(root, root.val)
    return True         # arbitrary choice

Follow up:

Solve it both recursively and iteratively.

Code

In [5]:

def is_unival_tree(root):
    """Recursive approach (DFS)"""
    if not root:
        return True         # arbitrary choice

    x = root.val
    stack = [root]
    while stack:
        node = stack.pop()
        if node.val != x:
            return False
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return True

In [6]:

def is_unival_tree(root):
    """alternative version of above solution."""
    if not root:
        return True         # arbitrary choice

    x = root.val
    stack = [root]
    while stack:
        node = stack.pop()
        if not node:
            continue
        if node.val != x:
            return False
        stack += node.left, node.right
    return True

In [7]:

def is_unival_tree(root):
    """Recursive approach (BFS)"""
    if not root:
        return True

    x = root.val
    queue = [root]
    for node in queue:              # DIFF HERE
        if not node:
            continue
        if node.val != x:
            return False
        queue += node.left, node.right
    return True