# Insertion Sort in Ruby – Code snippet

Popular insertion sort algorithm written in Ruby.

``sampleList = [12, 11, 13, 5, 6]sortedSampleList = []sampleList.each_with_index do |inputtedItem, inputtedItemIndex|    if sortedSampleList.length == 0        sortedSampleList.insert(0, inputtedItem)        next     end    sortedSampleList.each_with_index do |outputtedItem, outputtedItemIndex|        if inputtedItem < outputtedItem             sortedSampleList.insert(outputtedItemIndex, inputtedItem)            break        elsif outputtedItemIndex == sortedSampleList.length - 1             sortedSampleList.insert(sortedSampleList.length, inputtedItem)            break        end    endendp sampleList p sortedSampleList``

The output is the following.

``% ruby insertionSort.rb[12, 11, 13, 5, 6][5, 6, 11, 12, 13]``

# Determine if two numbers sum to given value in Binary Search Tree problem

Saw this problem in LeetCode.

Problem statement:

Given the `root` of a Binary Search Tree and a target number `k`, return `true` if there exist two elements in the BST such that their sum is equal to the given target.

Python based solution:

``````# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:

def find(self, root: TreeNode, k: int, alreadyUsed: TreeNode) -> bool:
if root.val == k and root is not alreadyUsed:
return True
if k < root.val and root.left is not None:
if k >= root.val and root.right is not None:
return False

def findInPart(self, part: TreeNode, root : TreeNode, k: int) -> bool:
toFind = k - part.val;
if self.find(root, toFind, part):
return True
if part.left is not None and self.findInPart(part.left, root, k):
return True
if part.right is not None and self.findInPart(part.right, root, k):
return True
return False

def findTarget(self, root: TreeNode, k: int) -> bool:
toFind = k - root.val;
if self.find(root, toFind, root):
return True
if root.left is not None and self.findInPart(root.left, root, k):
return True
if root.right is not None and self.findInPart(root.right, root, k):
return True
return False``````

This is a very simple solution.

The solution given here has time complexity of O(n Log n) for average case assuming the binary search tree is somewhat balanced. Space complexity is O(1) as I don’t allocate any new data structure.

By keeping track of the the elements you have already seen in a Set as you are doing the traversal you can improve the time complexity here to O(n) with space complexity of O(n).