Testing whether every left child's value is less than the right child's value in a binary tree

Question

Accepted Answer

To test if every left child's value is less than the right child's value in a binary tree.

Traverse the binary tree using any traversal algorithm (e.g., in-order, pre-order, post-order)
Compare the value of each left child with its right child
If any left child's value is greater than or equal to its right child's value, return false
If all left child's values are less than their right child's values, return true

Accepted Answer

class TreeNode:

def init(self, value):

self.value = value

self.left = None

self.right = None

def is_binary_search_tree(root):

def is_binary_search_tree_helper(node, min_value=float('-inf'), max_value=float('inf')):

if node is None:

return True

if node.value <= min_value or node.value >= max_value:

return False

# For the left child, the maximum allowed value is the current node's value

# For the right child, the minimum allowed value is the current node's value

return (is_binary_search_tree_helper(node.left, min_value, node.value) and

is_binary_search_tree_helper(node.right, node.value, max_value))

return is_binary_search_tree_helper(root)

# Example usage:

root = TreeNode(10)

root.left = TreeNode(5)

root.right = TreeNode(15)

root.left.left = TreeNode(3)

root.left.right = TreeNode(7)

root.right.left = TreeNode(12)

root.right.right = TreeNode(17)

result = is_binary_search_tree(root)

print(result) # Output should be True for this example

Top Microsoft Corporation Software Engineer interview questions & answers