Universal Value Binary Tree

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