Teaching Kids Programming – Breadth First Search Algorithm to Determine a Univalue Binary Tree

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a binary tree root, return whether all values in the tree are the same.

Constraints
n ≤ 100,000 where n is the number of nodes in root

univalued-binary-tree

Determine a Univalue Binary Tree via Breadth First Search Algorithm

The Breadth First Search Algorithm traverses the binary tree level by level. We then add all the numbers we have met into a hash set, once it contains more than 1 unique numbers, we failed the validation immediately.

Otherwise, we return true when there is none in the queue to proceed i.e. the standard Breadth First Search implementation via a queue.

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isUnivalueBinaryTree(self, root):
        if not root:
            return True
        q = deque([root])
        data = set()
        while len(q) > 0:
            p = q.popleft()
            data.add(p.val)
            if len(data) > 1:
                return False
            if p.left:
                q.append(p.left)
            if p.right:
                q.append(p.right)
        return True

The time complexity is O(N), as there are N nodes in the binary tree. The space complexity is O(N) as we are using a queue to implement the BFS, and the set will only be counted as O(1) as we will exit as long as there is more than 1 distinct numbers in the set.

We can remove the early exit check and only check after we finish the traverse:

# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def solve(self, root):
        if not root:
            return True
        q = deque([root])
        data = set()
        while len(q) > 0:
            p = q.popleft()
            data.add(p.val)
            if p.left:
                q.append(p.left)
            if p.right:
                q.append(p.right)
        return len(data) == 1

See also: How to Count Univalue Subtrees in a Binary Tree?

We can solve this problem using the Depth First Search Algorithm: Teaching Kids Programming – Depth First Search Algorithms to Determine a Univalue Binary Tree

–EOF (The Ultimate Computing & Technology Blog) —