# 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
```