You've successfully subscribed to Nicholas Workshop
Great! Next, complete checkout for full access to Nicholas Workshop
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

Universal Value Binary Tree

Nicholas Wong
Nicholas Wong

Question

Design an algorithm to verify that a tree is a universal value binary tree. Universal value binary tree means all value in that tree is the same.

Solution

There is two approach for this problem. One is with recursive function and another is with iterative function. For this problem, iterative function makes simpler answer. However, we have to learn using recursive function because in production code recursive function uses memory more efficiently while compared to iterative function.

Sample

# node structure 
class Node: 
	value = None 
	left = None 
	right = None  
	def __init__(self, value, left=None, right=None): 
		self.value = value 
		self.left = left 
		self.right = right 

# iterative way to solve this problem 
def iteratively_verify_universal_value_binary_tree(root): 
	stack = [root] 
	while len(stack) > 0: 
		node = stack.pop() 
		if node.value != root.value: return False 
		if node.left: stack.append(node.left) 
		if node.right: stack.append(node.right) 
	return True 

# recursive method to solve this problem 
def recursively_verify_universal_value_binary_tree(node, root_value=None): 
	if not node: return True 
	if not root_value: root_value = node.value # set root value to compared with 
	left_is_universal = recursively_verify_universal_value_binary_tree(node.left, root_value) # get left result 
	right_is_universal = recursively_verify_universal_value_binary_tree(node.right, root_value) # get right result 
	this_is_universal = node.value == root_value # get this result 
	return left_is_universal and right_is_universal and this_is_universal # combine result 

# trees 
universal_value_tree = Node(1, Node(1, Node(1), Node(1)), Node(1, Node(1), Node(1))) 
non_universal_value_tree = Node(1, Node(1, Node(1), Node(2)), Node(1, Node(1), Node(1))) 

# testing 
print iteratively_verify_universal_value_binary_tree(universal_value_tree) # true 
print iteratively_verify_universal_value_binary_tree(non_universal_value_tree) # false 
print recursively_verify_universal_value_binary_tree(universal_value_tree) # true 
print recursively_verify_universal_value_binary_tree(non_universal_value_tree) # false
Algorithm

Nicholas Wong

Fullstack software engineer with strong background in computer science and extensive experience in software engineering and architecture. Studied in NYU, worked in Yahoo, Rakuten and Manulife.