diff options
| author | mo <mokha@cisco.com> | 2017-08-08 14:11:14 -0600 |
|---|---|---|
| committer | mo <mokha@cisco.com> | 2017-08-08 14:11:14 -0600 |
| commit | 1aee88ccfa30d6733613ecbfa5b1578057afefae (patch) | |
| tree | 68da275060f7e4a06dac7e90f5c525df7244a733 /spec/binary_trees | |
| parent | 98b83a0e1474289b1574fe2d7c28ef36de55ec36 (diff) | |
solve using recursion.
Diffstat (limited to 'spec/binary_trees')
| -rw-r--r-- | spec/binary_trees/kth_largest_in_bst_spec.rb | 16 |
1 files changed, 15 insertions, 1 deletions
diff --git a/spec/binary_trees/kth_largest_in_bst_spec.rb b/spec/binary_trees/kth_largest_in_bst_spec.rb index 0f6699a..c4dae2b 100644 --- a/spec/binary_trees/kth_largest_in_bst_spec.rb +++ b/spec/binary_trees/kth_largest_in_bst_spec.rb @@ -118,9 +118,23 @@ describe "#kth_largest_in_bst" do all[k + 1] end + def leaf?(tree) + tree.left&.nil? && tree.right&.nil? + end + + def to_array(tree) + return [] if tree.nil? + return [tree.value] if leaf?(tree) + to_array(tree.left) + [tree.value] + to_array(tree.right) + end + + def kth_largest_in_bst(tree, k) + to_array(tree)[k - 1] + end + [ { 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 }, - { 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: -1 }, + { 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 }, { t: { "value": 100, "left": nil, "right": nil }, k: 1, x: 100 }, { t: { "value": 1, "left": { "value": 0, "left": nil, "right": nil }, "right": { "value": 2, "left": nil, "right": nil } }, k: 3, x: 2 }, { t: { "value": 1, "left": { "value": 0, "left": nil, "right": nil }, "right": { "value": 2, "left": nil, "right": nil } }, k: 2, x: 1 }, |