-
Notifications
You must be signed in to change notification settings - Fork 0
/
binary_tree_serializer_test.py
65 lines (51 loc) · 2.4 KB
/
binary_tree_serializer_test.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
from binary_tree_serializer import TreeNode, BinaryTreeSerializer
import unittest
from copy import deepcopy
class BinaryTreeSerializerTest(unittest.TestCase):
def setUp(self) -> None:
"""
Sample binary tree and equivalent string representation
"""
self.bts = BinaryTreeSerializer()
self.node = TreeNode(1)
self.node.left, self.node.right = TreeNode(2), TreeNode(3)
self.node.right.left, self.node.right.right = TreeNode(4), TreeNode(5)
self.str_repr = '1,2,3,x,x,4,5,x,x,x,x'
def test_serialize(self):
self.assertEqual(self.bts.serialize(self.node), self.str_repr)
def test_deserialize(self):
self.assertTrue(self.is_same_binary_tree(self.bts.deserialize(self.str_repr), self.node))
def test_recover_binary_tree(self):
"""
Tests serialization and deserialization sequentially
"""
self.assertTrue(self.is_same_binary_tree(self.bts.deserialize(self.bts.serialize(self.node)), self.node))
self.assertEqual(self.bts.serialize(self.bts.deserialize(self.str_repr)), self.str_repr)
def is_same_binary_tree(self, node1, node2):
"""
Tests whether two binary trees are identical; necessary because they occupy different memory addresses
Operates in linear O(n) time via recursion
"""
if not node1 and not node2:
return True
if node1 and node2:
is_same_curr_node = (node1.val == node2.val)
is_same_left_node = self.is_same_binary_tree(node1.left, node2.left)
is_same_right_node = self.is_same_binary_tree(node1.right, node2.right)
return is_same_curr_node and is_same_left_node and is_same_right_node
return False
def test_is_same_binary_tree(self):
"""
Tests is_same_binary_tree helper function.
"""
self.assertTrue(self.is_same_binary_tree(self.node, deepcopy(self.node)))
left_only = TreeNode(1)
left_only.left = TreeNode(2)
right_only = TreeNode(1)
right_only.right = TreeNode(2)
self.assertFalse(self.is_same_binary_tree(left_only, right_only))
self.assertFalse(self.is_same_binary_tree(TreeNode(0), TreeNode(1)))
self.assertTrue(self.is_same_binary_tree(TreeNode(1), TreeNode(1)))
self.assertFalse(self.is_same_binary_tree(TreeNode(1), right_only))
if __name__ == "__main__":
unittest.main()