Binary tree insert, visualizer, and decomposition into doubly-linked cycle

gistfile1.rb

# encoding: UTF-8
def tree_insert(root, v)
  if !root[:v]
    root.clear
    root.merge!(
      :v => v,
      :p => nil,
      :n => nil
    )
  elsif root[:v] > v
    if root[:p]
      tree_insert(root[:p], v)
    else
      root[:p] = {
        :v => v,
        :p => nil,
        :n => nil,
      }
    end
  elsif root[:v] < v
    if root[:n]
      tree_insert(root[:n], v)
    else
      root[:n] = {
        :v => v,
        :p => nil,
        :n => nil
      }
    end
  else # v == root[:v]
    if !root[:n]
      root[:n] = {
        :v => v,
        :p => nil,
        :n => nil,
      }
    elsif !root[:p]
      root[:p] = {
        :v => v,
        :p => nil,
        :n => nil
      }
    else
      tree_insert(root[:n], v)
    end
  end
  root
end

def bst_to_dll_cycle(tree)
  min = tree
  max = tree

  p = tree[:p]
  n = tree[:n]

  if p
    prev_cycle = bst_to_dll_cycle(p)
    min = prev_cycle
    tree[:p] = prev_cycle[:p] # the max value of prev_cycle
    prev_cycle[:p][:n] = tree
  end

  if n
    next_cycle = bst_to_dll_cycle(n)
    max = next_cycle[:p]
    tree[:n] = next_cycle # the min of next_cycle
    next_cycle[:p] = tree
  end

  max[:n] = min
  min[:p] = max  

  min
end

def propagate_offsets_and_get_width(tree, x_offset = 0, y_offset = 0)
  width_left = tree[:p] ? propagate_offsets_and_get_width(tree[:p], x_offset, y_offset + 1) : 0 
  tree[:x] = x_offset + width_left
  tree[:y] = y_offset
  width_right = tree[:n] ? propagate_offsets_and_get_width(tree[:n], tree[:x] + 1, y_offset + 1) : 0
  width_left + 1 + width_right
end

def print_x(cursor_x, target_x, char, fill)
  (target_x - cursor_x).times { print fill }
  print char
  target_x + 1
end

def print_tree(tree)
  propagate_offsets_and_get_width(tree)

  left_child_marker = '⌜'
  right_child_marker = '⌝'
  branch_marker = '·'
  blank_marker = ' '

  y = 0
  x = 0 
  queue = [ tree ]

  begin
    q = queue.shift

    if q[:y] != y
      print "\n"
      y = q[:y]
      x = 0
    end
    
    node_left_fill = blank_marker

    if (p = q[:p])
      x = print_x(x, p[:x], left_child_marker, blank_marker)
      node_left_fill = branch_marker
      queue << p
    end
    
    x = print_x(x, q[:x], q[:v], node_left_fill)
   
    if (n = q[:n])
      x = print_x(x, n[:x], right_child_marker, branch_marker) 
      queue << n
    end
  end until queue.empty?

  print "\n"
end

def dll_cycle_vals(dll_cycle)
  first = dll_cycle
  n = first 
  vals = []

  begin
    vals << n[:v]
    n = n[:n]
  end until (n.nil? || n == first)

  vals
end

randoms = (0..64).map { rand(0..9) }
puts "values: #{randoms}"

# Insert into tree
tree = {}
randoms.each { |v| tree_insert(tree, v) }
print_tree(tree)

# Create cycle and print
dll_cycle = bst_to_dll_cycle(tree)
cycle_vals = dll_cycle_vals(dll_cycle)
puts "sorted: #{cycle_vals}"