Skip to content

Instantly share code, notes, and snippets.

@cshtdd
Created February 25, 2020 16:22
Show Gist options
  • Save cshtdd/814cf5da31e6e46b9a89fceb9132a0c8 to your computer and use it in GitHub Desktop.
Save cshtdd/814cf5da31e6e46b9a89fceb9132a0c8 to your computer and use it in GitHub Desktop.
Find the kth smallest element in a binary tree
#!/bin/ruby
class Node
attr_accessor :value
attr_accessor :left
attr_accessor :right
def initialize(value)
self.value = value
end
end
def inorder(root)
if not root.left.nil?
inorder(root.left)
end
puts root.value
if not root.right.nil?
inorder(root.right)
end
end
def ksmallest(root, k)
l = []
_ksmallest(root, k, l)
l[k - 1]
end
def _ksmallest(root, k, l)
if not root.left.nil?
_ksmallest(root.left, k, l)
end
l << root.value
if not root.right.nil?
_ksmallest(root.right, k, l)
end
end
def add(value, root)
if root.nil?
return Node.new( value)
else
if value > root.value
if root.right.nil?
root.right = Node.new(value)
else
add(value, root.right)
end
else
if root.left.nil?
root.left = Node.new(value)
else
add(value, root.left)
end
end
end
end
puts 'Program Start'
# 7
# 3 9
# 1 4
root = add(7, nil)
add(3, root)
add(4, root)
add(1, root)
add(9, root)
inorder(root)
n = ksmallest(root, 3)
puts "3rd smallest: #{n}"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment