Interview Practice Extra 03 – 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)

# main
root = node_08
print depth_first_traversal(root)
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: