diff options
Diffstat (limited to 'universe/data_structures_and_algorithms/balanced-binary-tree.py')
| -rw-r--r-- | universe/data_structures_and_algorithms/balanced-binary-tree.py | 145 |
1 files changed, 0 insertions, 145 deletions
diff --git a/universe/data_structures_and_algorithms/balanced-binary-tree.py b/universe/data_structures_and_algorithms/balanced-binary-tree.py deleted file mode 100644 index 01fd965fd540..000000000000 --- a/universe/data_structures_and_algorithms/balanced-binary-tree.py +++ /dev/null @@ -1,145 +0,0 @@ -import unittest -from itertools import combinations - - -def balanced(xs): - """Return True if `xs` contains no two values that differ by more than - one.""" - if len(xs) == 0 or len(xs) == 1: - return True - if len(xs) == 2: - return math.abs(xs[0] - xs[1]) <= 1 - else: - pass - - -def is_leaf(node): - return node.left is None and node.right is None - - -def is_balanced(tree_root): - """Returns True if the difference between the depths of any two leaf nodes - does not exceed 1.""" - depths = set() - populate_depths(tree_root, 0, depths) - - # cartesian product - only the top half - for diff in set(abs(a - b) for a, b in combinations(depths, 2)): - if diff > 1: - return False - - return True - - -def populate_depths(node, depth, depths): - if is_leaf(node): - depths.add(depth) - else: - if node.left is not None: - populate_depths(node.left, depth + 1, depths) - if node.right is not None: - populate_depths(node.right, depth + 1, depths) - - -################################################################################ -# 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_full_tree(self): - tree = Test.BinaryTreeNode(5) - left = tree.insert_left(8) - right = tree.insert_right(6) - left.insert_left(1) - left.insert_right(2) - right.insert_left(3) - right.insert_right(4) - result = is_balanced(tree) - self.assertTrue(result) - - def test_both_leaves_at_the_same_depth(self): - tree = Test.BinaryTreeNode(3) - left = tree.insert_left(4) - right = tree.insert_right(2) - left.insert_left(1) - right.insert_right(9) - result = is_balanced(tree) - self.assertTrue(result) - - def test_leaf_heights_differ_by_one(self): - tree = Test.BinaryTreeNode(6) - left = tree.insert_left(1) - right = tree.insert_right(0) - right.insert_right(7) - result = is_balanced(tree) - self.assertTrue(result) - - def test_leaf_heights_differ_by_two(self): - tree = Test.BinaryTreeNode(6) - left = tree.insert_left(1) - right = tree.insert_right(0) - right_right = right.insert_right(7) - right_right.insert_right(8) - result = is_balanced(tree) - self.assertFalse(result) - - def test_three_leaves_total(self): - tree = Test.BinaryTreeNode(1) - left = tree.insert_left(5) - right = tree.insert_right(9) - right.insert_left(8) - right.insert_right(5) - result = is_balanced(tree) - self.assertTrue(result) - - def test_both_subtrees_superbalanced(self): - tree = Test.BinaryTreeNode(1) - left = tree.insert_left(5) - right = tree.insert_right(9) - right_left = right.insert_left(8) - right.insert_right(5) - right_left.insert_left(7) - result = is_balanced(tree) - self.assertFalse(result) - - def test_both_subtrees_superbalanced_two(self): - tree = Test.BinaryTreeNode(1) - left = tree.insert_left(2) - right = tree.insert_right(4) - left.insert_left(3) - left_right = left.insert_right(7) - left_right.insert_right(8) - right_right = right.insert_right(5) - right_right_right = right_right.insert_right(6) - right_right_right.insert_right(9) - result = is_balanced(tree) - self.assertFalse(result) - - def test_only_one_node(self): - tree = Test.BinaryTreeNode(1) - result = is_balanced(tree) - self.assertTrue(result) - - def test_linked_list_tree(self): - tree = Test.BinaryTreeNode(1) - right = tree.insert_right(2) - right_right = right.insert_right(3) - right_right.insert_right(4) - result = is_balanced(tree) - self.assertTrue(result) - - -unittest.main(verbosity=2) |