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 rootunivalued-binary-tree
This post talks about using DFS algorithm to determine a univalue binary tree: Determine a Univalue Binary Tree via Recursive Depth First Search Algorithms
Determine Univalue Binary Tree using Depth First Search Algorithm
We can traverse the binary tree using depth first search algorithm. We pass the root and its value (unique value aka univalue) down the tree, and return False if any of the nodes in the subtrees does not equal to it.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | # 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 def dfs(root, v): if not root: return True if root.val != v: return False return dfs(root.left, v) and dfs(root.right, v) return dfs(root, root.val) |
# 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
def dfs(root, v):
if not root:
return True
if root.val != v:
return False
return dfs(root.left, v) and dfs(root.right, v)
return dfs(root, root.val)We can also let the DFS function return the set of values – thus we can union recursive sets and check if the set contains only one number.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | # 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): def dfs(root): if not root: return set() data = set([root.val]) data = data.union(dfs(root.left)) data = data.union(dfs(root.right)) return data data = dfs(root) return len(data) == 1 |
# 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):
def dfs(root):
if not root:
return set()
data = set([root.val])
data = data.union(dfs(root.left))
data = data.union(dfs(root.right))
return data
data = dfs(root)
return len(data) == 1With slight different implementation – where we move the set into a different scope and reference it using nonlocal keyword.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | # 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): data = set() def dfs(root): if not root: return nonlocal data data.add(root.val) dfs(root.left) dfs(root.right) dfs(root) return len(data) == 1 |
# 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):
data = set()
def dfs(root):
if not root:
return
nonlocal data
data.add(root.val)
dfs(root.left)
dfs(root.right)
dfs(root)
return len(data) == 1All above DFS implementations require O(N) time where N is the number of the nodes in the given binary tree. The first implementation of DFS require O(1) time (disregard the usage of implicit stack by recursion). The last 2 implementations require O(N) space as a set is used.
We can also solve this problem by using Breadth First Search Algorithm: Teaching Kids Programming – Breadth First Search Algorithm to Determine a Univalue Binary Tree
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Noisy Palindrome Algorithm (Check Lowercase Palindrome Strings)
Next Post: Determine Color of a Chessboard Square
