diff options
| -rw-r--r-- | scratch/deepmind/part_two/bst-checker.py | 110 | ||||
| -rw-r--r-- | scratch/deepmind/part_two/todo.org | 4 |
2 files changed, 112 insertions, 2 deletions
diff --git a/scratch/deepmind/part_two/bst-checker.py b/scratch/deepmind/part_two/bst-checker.py new file mode 100644 index 000000000000..fd0374a9ce91 --- /dev/null +++ b/scratch/deepmind/part_two/bst-checker.py @@ -0,0 +1,110 @@ +import unittest +from collections import deque + + +# While this function solves the problem, it uses O(n) space since we're storing +# all of the less-thans and greater-thans. +def is_binary_search_tree_first_attempt(root): + q = deque() + q.append((set(), set(), root)) + + while q: + lts, gts, node = q.popleft() + + if not all([node.value < lt for lt in lts]): + return False + if not all([node.value > gt for gt in gts]): + return False + + if node.left: + q.append((lts | {node.value}, gts, node.left)) + if node.right: + q.append((lts, gts | {node.value}, node.right)) + + return True + + +# While I did not originally solve this problem this way, when I learned that I +# could condense the space of my solution's runtime, I wrote this. +def is_binary_search_tree(root): + q = deque() + q.append((None, None, root)) + + while q: + lt, gt, node = q.popleft() + + if not lt is None and node.value >= lt: + return False + if not gt is None and node.value <= gt: + return False + + if node.left: + q.append((node.value, gt, node.left)) + if node.right: + q.append((lt, node.value, node.right)) + + return True + + +# Tests +class Test(unittest.TestCase): + class BinaryTreeNode(object): + def __init__(self, value): + self.value = value + self.left = None + self.right = None + + def insert_left(self, value): + self.left = Test.BinaryTreeNode(value) + return self.left + + def insert_right(self, value): + self.right = Test.BinaryTreeNode(value) + return self.right + + def test_valid_full_tree(self): + tree = Test.BinaryTreeNode(50) + left = tree.insert_left(30) + right = tree.insert_right(70) + left.insert_left(10) + left.insert_right(40) + right.insert_left(60) + right.insert_right(80) + result = is_binary_search_tree(tree) + self.assertTrue(result) + + def test_both_subtrees_valid(self): + tree = Test.BinaryTreeNode(50) + left = tree.insert_left(30) + right = tree.insert_right(80) + left.insert_left(20) + left.insert_right(60) + right.insert_left(70) + right.insert_right(90) + result = is_binary_search_tree(tree) + self.assertFalse(result) + + def test_descending_linked_list(self): + tree = Test.BinaryTreeNode(50) + left = tree.insert_left(40) + left_left = left.insert_left(30) + left_left_left = left_left.insert_left(20) + left_left_left.insert_left(10) + result = is_binary_search_tree(tree) + self.assertTrue(result) + + def test_out_of_order_linked_list(self): + tree = Test.BinaryTreeNode(50) + right = tree.insert_right(70) + right_right = right.insert_right(60) + right_right.insert_right(80) + result = is_binary_search_tree(tree) + self.assertFalse(result) + + def test_one_node_tree(self): + tree = Test.BinaryTreeNode(50) + result = is_binary_search_tree(tree) + self.assertTrue(result) + + +unittest.main(verbosity=2) diff --git a/scratch/deepmind/part_two/todo.org b/scratch/deepmind/part_two/todo.org index 3ddd9206ac9d..97b5e6fad3c2 100644 --- a/scratch/deepmind/part_two/todo.org +++ b/scratch/deepmind/part_two/todo.org @@ -22,7 +22,7 @@ ** DONE Merging Meeting Times * Trees and graphs ** DONE Balanced Binary Tree -** TODO Binary Search Tree Checker +** DONE Binary Search Tree Checker ** TODO 2nd Largest Item in a Binary Search Tree ** TODO Graph Coloring ** TODO MeshMessage @@ -33,7 +33,7 @@ ** TODO Making Change ** TODO The Cake Thief ** DONE Balanced Binary Tree -** TODO Binary Search Tree Checker +** DONE Binary Search Tree Checker ** TODO 2nd Largest Item in a Binary Search Tree * Queues and stacks ** TODO Largest Stack |