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)

Show Comments