blob: bc167d975a7b3ed40e3a944dce2ca90fb6836e41 (
plain) (
blame)
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
|
import unittest
from collections import deque
################################################################################
# Implementation
################################################################################
def is_leaf(node):
return node.left is None and node.right is None
def find_largest(node):
current = node
while current.right is not None:
current = current.right
return current.value
def find_second_largest(node):
history = deque()
current = node
while current.right:
history.append(current)
current = current.right
if current.left:
return find_largest(current.left)
elif history:
return history.pop().value
else:
raise TypeError
def find_second_largest_backup(node):
history = deque()
current = node
# traverse -> largest
while current.right:
history.append(current)
current = current.right
if current.left:
return find_largest(current.left)
elif history:
return history.pop().value
else:
raise ArgumentError
# Write a iterative version to avoid consuming memory with the call stack.
# Commenting out the recursive code for now.
def find_second_largest_backup(node):
if node.left is None and node.right is None:
raise ArgumentError
elif node.right is None and is_leaf(node.left):
return node.left.value
# recursion
# elif node.right is None:
# return find_largest(node.left)
# iterative version
elif node.right is None:
current = node.left
while current.right is not None:
current = current.right
return current.value
# recursion
# TODO: Remove recursion from here.
elif not is_leaf(node.right):
return find_second_largest(node.right)
# could do an else here, but let's be more assertive.
elif is_leaf(node.right):
return node.value
else:
raise ArgumentError
################################################################################
# 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(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)
actual = find_second_largest(tree)
expected = 70
self.assertEqual(actual, expected)
def test_largest_has_a_left_child(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)
actual = find_second_largest(tree)
expected = 60
self.assertEqual(actual, expected)
def test_largest_has_a_left_subtree(self):
tree = Test.BinaryTreeNode(50)
left = tree.insert_left(30)
right = tree.insert_right(70)
left.insert_left(10)
left.insert_right(40)
right_left = right.insert_left(60)
right_left_left = right_left.insert_left(55)
right_left.insert_right(65)
right_left_left.insert_right(58)
actual = find_second_largest(tree)
expected = 65
self.assertEqual(actual, expected)
def test_second_largest_is_root_node(self):
tree = Test.BinaryTreeNode(50)
left = tree.insert_left(30)
tree.insert_right(70)
left.insert_left(10)
left.insert_right(40)
actual = find_second_largest(tree)
expected = 50
self.assertEqual(actual, expected)
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)
actual = find_second_largest(tree)
expected = 40
self.assertEqual(actual, expected)
def test_ascending_linked_list(self):
tree = Test.BinaryTreeNode(50)
right = tree.insert_right(60)
right_right = right.insert_right(70)
right_right.insert_right(80)
actual = find_second_largest(tree)
expected = 70
self.assertEqual(actual, expected)
def test_error_when_tree_has_one_node(self):
tree = Test.BinaryTreeNode(50)
with self.assertRaises(Exception):
find_second_largest(tree)
def test_error_when_tree_is_empty(self):
with self.assertRaises(Exception):
find_second_largest(None)
unittest.main(verbosity=2)
|
