You've successfully subscribed to Nicholas Workshop
Great! Next, complete checkout for full access to Nicholas Workshop
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

Verify Binary Tree with Same Value

Nicholas Wong
Nicholas Wong

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)
Algorithm

Nicholas Wong

Fullstack software engineer with strong background in computer science and extensive experience in software engineering and architecture. Studied in NYU, worked in Yahoo, Rakuten and Manulife.