Just another interview question that I had to code in Ruby :)

problem.md

Just another interview problem ..

Given the following code:

def bst_distance(values, n, node1, node2)
  # write you code here
end

Fix this problem:

solution.rb

class Node
  attr_accessor :value, :left, :right
  def initialize(value, left, right)
    @value = value
    @left = left
    @right = right
  end

  def self.from_array(arr)
    return if arr.empty?
    value = arr.shift
    left_elems, right_elems = arr.partition { |elem| value > elem }
    left = from_array(left_elems) unless left_elems.empty?
    right = from_array(right_elems) unless right_elems.empty?
    new(value, left, right)
  end

  # for debugging only
  def to_s
    "#{@value}{#{@left}|#{@right}}"
  end

  def self.path(root, val)
    current_node = root
    path = []
    until current_node.nil?
      path.push(current_node.value)
      return path if val == current_node.value
      current_node = val > current_node.value ? current_node.right : current_node.left
    end
    []
  end
end

# bst_distance(values, values_count, node1, node2)
def bst_distance(values, _, node1, node2)
  tree = Node.from_array(values)
  return -1 if tree.nil?
  path1 = Node.path(tree, node1)
  path2 = Node.path(tree, node2)
  return -1 unless path1.size.positive? && path2.size.positive?
  shared_path = path1 & path2
  uniq_path1 = path1 - shared_path
  uniq_path2 = path2 - shared_path
  uniq_path1.size + uniq_path2.size
end


puts bst_distance([5, 6, 3, 1, 2, 4], 5, 2, 4) # should return 3
puts bst_distance([5, 1], 2, 5, 1) # should return 1
puts bst_distance([], 0, 5, 1) # should return -1
puts bst_distance([1, 5, 3], 3, 1, 1) # should return 0
puts bst_distance([1, 5, 3], 3, 2, 1) # should return -1