master
1<<-DOC
2Note: Your solution should have only one BST traversal and O(1) extra space complexity,
3since this is what you will be asked to accomplish in an interview.
4
5A tree is considered a binary search tree (BST) if for each of its nodes the following is true:
6
7The left subtree of a node contains only nodes with keys less than the node's key.
8The right subtree of a node contains only nodes with keys greater than the node's key.
9Both the left and the right subtrees must also be binary search trees.
10Given a binary search tree t, find the kth largest element in it.
11
12Note that kth largest element means kth element in increasing order. See examples for better understanding.
13
14Example
15
16For
17
18t = {
19 "value": 3,
20 "left": {
21 "value": 1,
22 "left": null,
23 "right": null
24 },
25 "right": {
26 "value": 5,
27 "left": {
28 "value": 4,
29 "left": null,
30 "right": null
31 },
32 "right": {
33 "value": 6,
34 "left": null,
35 "right": null
36 }
37 }
38}
39and k = 2, the output should be
40kthLargestInBST(t, k) = 3.
41
42Here is what t looks like:
43
44 3
45 / \
461 5
47 / \
48 4 6
49The values of t are [1, 3, 4, 5, 6], and the 2nd element when the values are in sorted order is 3.
50
51For
52
53t = {
54 "value": 1,
55 "left": {
56 "value": -1,
57 "left": {
58 "value": -2,
59 "left": null,
60 "right": null
61 },
62 "right": {
63 "value": 0,
64 "left": null,
65 "right": null
66 }
67 },
68 "right": null
69}
70
71and k = 1, the output should be
72kthLargestInBST(t, k) = -2.
73
74Here is what t looks like:
75
76 1
77 /
78 -1
79 / \
80-2 0
81The values of t are [-2, -1, 0, 1], and the 1st largest is -2.
82
83Input/Output
84
85[time limit] 4000ms (rb)
86[input] tree.integer t
87
88A tree of integers. It is guaranteed that t is a BST.
89
90Guaranteed constraints:
911 ≤ tree size ≤ 104,
92-105 ≤ node value ≤ 105.
93
94[input] integer k
95
96An integer.
97
98Guaranteed constraints:
991 ≤ k ≤ tree size.
100
101[output] integer
102
103The kth largest value in t
104DOC
105
106describe "#kth_largest_in_bst" do
107 def kth_largest_in_bst(tree, k)
108 puts tree.to_a.inspect
109 stack = [tree]
110 all = [ ]
111 until stack.empty?
112 node = stack.pop
113 all.push(node.value)
114 stack.push(node.left) if node.left
115 stack.push(node.right) if node.right
116 end
117 puts all.inspect
118 all[k + 1]
119 end
120
121 def to_array(tree)
122 return [] if tree.nil?
123 to_array(tree.left) + [tree.value] + to_array(tree.right)
124 end
125
126 def kth_largest_in_bst(tree, k)
127 to_array(tree)[k - 1]
128 end
129
130 class Traversal
131 attr_reader :k
132
133 def initialize(k)
134 @counter = 0
135 @k = k
136 end
137
138 def traverse(tree)
139 return if tree.nil?
140
141 if @counter < k && result = traverse(tree.left)
142 return result
143 end
144
145 @counter += 1
146 return tree.value if @counter == k
147
148 traverse(tree.right) if @counter < k
149 end
150 end
151
152 def kth_largest_in_bst(tree, k)
153 Traversal.new(k).traverse(tree)
154 end
155
156 def traverse(node, yielder)
157 return if node.nil?
158
159 traverse(node.left, yielder)
160 yielder.yield node.value
161 traverse(node.right, yielder)
162 end
163
164 def kth_largest_in_bst(tree, k)
165 x = Enumerator.new { |yielder| traverse(tree, yielder) }
166 (k-1).times { x.next }
167 x.next
168 end
169
170 [
171 { t: { "value": 3, "left": { "value": 1, "left": nil, "right": nil }, "right": { "value": 5, "left": { "value": 4, "left": nil, "right": nil }, "right": { "value": 6, "left": nil, "right": nil } } }, k: 2, x: 3 },
172 { t: { "value": 1, "left": { "value": -1, "left": { "value": -2, "left": nil, "right": nil }, "right": { "value": 0, "left": nil, "right": nil } }, "right": nil }, k: 1, x: -2 },
173 { t: { "value": 100, "left": nil, "right": nil }, k: 1, x: 100 },
174 { t: { "value": 1, "left": { "value": 0, "left": nil, "right": nil }, "right": { "value": 2, "left": nil, "right": nil } }, k: 3, x: 2 },
175 { t: { "value": 1, "left": { "value": 0, "left": nil, "right": nil }, "right": { "value": 2, "left": nil, "right": nil } }, k: 2, x: 1 },
176 { t: { "value": -2, "left": nil, "right": { "value": 3, "left": { "value": 2, "left": nil, "right": nil }, "right": nil } }, k: 1, x: -2 }
177 ].each do |x|
178 it do
179 expect(kth_largest_in_bst(Tree.build_from(x[:t]), x[:k])).to eql(x[:x])
180 end
181 end
182
183end