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

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

 

Leave a Reply

%d bloggers like this: