Interview Practice Extra 07 - 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 # 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

Show Comments