Verify Binary Tree with Same Value

Question

Verify whether all nodes have the same value in a binary tree.

Solution

We can traverse the tree with our usual way, like depth-first or breadth-first algorithm. Then pass a value, probably the root value, to compare with the visiting node.

Example

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

# what to do while visiting the node 
def visit(node, value): 
    return node.value == value # reflect a binary tree 

def depth_first_traversal(root): 
    stack = [root] 
    value = root.value 
    result = True 
    while len(stack) > 0: 
        node = stack.pop() 
        result = visit(node, value) 
        if result == False: break 
        if node.left: stack.append(node.left) 
        if node.right: stack.append(node.right) 
    return result 
                
# a binary tree with all values to be 1 
node_05 = bst_node(1)
node_07 = bst_node(1)
node_09 = bst_node(1)
node_11 = bst_node(1)
node_06 = bst_node(1, node_05, node_07)
node_10 = bst_node(1, node_09, node_11)
node_08 = bst_node(1, node_06, node_10) 
root = node_08 

# main 
print depth_first_traversal(root)