BSTChecker.py:def check_bst_validity(root_node): def is_violating_node(node, min_key=float('-inf'), max_key=float('inf'), ancestors=None): if ancestors is None: ancestors = set() if node is None: return None if not (min_key < node.key < max_key): return node if node.left in ancestors or node.right in ancestors: return node ancestors.add(node) left_violation = is_violating_node(node.left, min_key, node.key, ancestors) if left_violation: return left_violation right_violation = is_violating_node(node.right, node.key, max_key, ancestors) if right_violation: return right_violation ancestors.remove(node) return None return is_violating_node(root_node) 1:Compare outputkeyboard_arrow_up 1 / 1 Input (10, (20), (30, (29), (31))) Your output 20 2:Compare outputkeyboard_arrow_up 1 / 1 Input (20, (10), (30, (29), (31))) Your output None 3:Compare outputkeyboard_arrow_up 1 / 1 Input (80, (60, (40, (20, None, (50)), None), None), None) Your output 50 4:Unit testkeyboard_arrow_up 1 / 1 Valid tree with 10 nodes Test feedback check_bst_validity() returned None correctly. 5:Unit testkeyboard_arrow_up 1 / 1 Invalid tree with right child's key less than parent's key Test feedback check_bst_validity() returned the BST rule-violating node correctly. 6:Unit testkeyboard_arrow_up 1 / 1 Invalid tree with left child's key greater than parent's key Test feedback check_bst_validity() returned the BST rule-violating node correctly. 7:Unit testkeyboard_arrow_up 1 / 1 Invalid tree with lesser key in right subtree Test feedback check_bst_validity() returned the BST rule-violating node correctly. 8:Unit testkeyboard_arrow_up 0 / 1 Invalid tree with right child linking to ancestor Test feedback check_bst_validity() returned a node that is not the BST rule-violating node. The node with either the left or right attribute referencing an ancestor must be returned. 9:Unit testkeyboard_arrow_up 1 / 1 Invalid tree with left child linking to parent Test feedback check_bst_validity() returned the BST rule-violating node correctly. 10:Unit testkeyboard_arrow_up 1 / 1 Invalid tree with left child linking to ancestor Test feedback check_bst_validity() returned the BST rule-violating node correctly.
BSTChecker.py:
def check_bst_validity(root_node):
def is_violating_node(node, min_key=float('-inf'), max_key=float('inf'), ancestors=None):
if ancestors is None:
ancestors = set()
if node is None:
return None
if not (min_key < node.key < max_key):
return node
if node.left in ancestors or node.right in ancestors:
return node
ancestors.add(node)
left_violation = is_violating_node(node.left, min_key, node.key, ancestors)
if left_violation:
return left_violation
right_violation = is_violating_node(node.right, node.key, max_key, ancestors)
if right_violation:
return right_violation
ancestors.remove(node)
return None
return is_violating_node(root_node)
1:Compare outputkeyboard_arrow_up
1 / 1
Input
(10, (20), (30, (29), (31)))
Your output
20
2:Compare outputkeyboard_arrow_up
1 / 1
Input
(20, (10), (30, (29), (31)))
Your output
None
3:Compare outputkeyboard_arrow_up
1 / 1
Input
(80, (60, (40, (20, None, (50)), None), None), None)
Your output
50
4:Unit testkeyboard_arrow_up
1 / 1
Valid tree with 10 nodes
Test feedback
check_bst_validity() returned None correctly.
5:Unit testkeyboard_arrow_up
1 / 1
Invalid tree with right child's key less than parent's key
Test feedback
check_bst_validity() returned the BST rule-violating node correctly.
6:Unit testkeyboard_arrow_up
1 / 1
Invalid tree with left child's key greater than parent's key
Test feedback
check_bst_validity() returned the BST rule-violating node correctly.
7:Unit testkeyboard_arrow_up
1 / 1
Invalid tree with lesser key in right subtree
Test feedback
check_bst_validity() returned the BST rule-violating node correctly.
8:Unit testkeyboard_arrow_up
0 / 1
Invalid tree with right child linking to ancestor
Test feedback
check_bst_validity() returned a node that is not the BST rule-violating node. The node with either the left or right attribute referencing an ancestor must be returned.
9:Unit testkeyboard_arrow_up
1 / 1
Invalid tree with left child linking to parent
Test feedback
check_bst_validity() returned the BST rule-violating node correctly.
10:Unit testkeyboard_arrow_up
1 / 1
Invalid tree with left child linking to ancestor
Test feedback
check_bst_validity() returned the BST rule-violating node correctly.
AI-generated content may present inaccurate or offensive content that does not represent bartleby’s views.
Unlock instant AI solutions
Tap the button
to generate a solution
