about summary refs log tree commit diff
path: root/scratch/data_structures_and_algorithms/second-largest-item-bst.py
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)