class Node
  attr_accessor :value, :left, :right
  def initialize(val)
    @value = val   # ノードが保持する値
    @left = nil    # 左側のノード
    @right = nil   # 右側のノード
  end

  # 描画に必要な情報を計算 (内部用)
  def render_info(canvas, margin, x, y)
    # 左のノードがあれば、そのノード以下の木の横幅が返ってくる
    x = @left.render_info(canvas, margin, x, y + 1) + margin if @left

    # このノードの分の描画に必要な情報を追加
    canvas << [x, y, self]

    # このノードの分の描画に必要な情報を追加
    x += @value.to_s.size
    x = @right.render_info(canvas, margin, x + margin, y + 1) if @right

    # 呼び出した親のために横幅を返す
    x
  end
  protected :render_info

  # render_infoで描画情報を集めて返す (外部用)
  def render(margin)
    canvas = []
    render_info(canvas, margin, 0, 0)
    canvas
  end
end


def print_canvas(canvas)
  canvas = canvas.sort_by {|x, y, *| [y, x] }

  last_x = 0
  last_y = 0

  canvas.each do |x, y, node|
      text = node.value.to_s

    if y != last_y
      last_x = 0
      puts
    end

    print " " * (x - last_x)
    print text

    last_x = x + text.to_s.size
    last_y = y
  end
  puts
end

def print_canvas2(canvas)
  canvas = canvas.sort_by {|x, y, *| [y, x] }

  last_x = 0
  last_y = 0

  canvas.each do |x, y, node|
    text = node.value.to_s

    if y != last_y
      last_x = 0
      puts
    end

    if node.left
      ileft = canvas.index {|nx, ny, *| y + 1 == ny && x <= nx } - 1
      left_x, * = canvas[ileft]
      left_x_end = left_x + node.left.value.to_s.size
      print " " * (left_x_end - last_x)
      print "_" * (x - left_x_end)
    else
      print " " * (x - last_x)
    end

    print text

    x += text.to_s.size

    if node.right
      iright = canvas.index {|nx, ny, *| y + 1 == ny && x <= nx }
      right_x, * = canvas[iright]

      print "_" * (right_x - x)
      x = right_x
    end

    last_x = x
    last_y = y
  end
  puts
end

def print_canvas3(canvas)
  canvas = canvas.sort_by {|x, y, *| [y, x] }
  canvas_lines = canvas.group_by {|x, y, *| y }.sort.map {|_, line| line }

  canvas_lines.each do |line|
    slashes = []

    last_x = 0
    line.each do |x, y, node|
      text = node.value.to_s

      if node.left
        next_line = canvas_lines[y + 1]
        ileft = next_line.index {|nx, *| x <= nx } - 1
        left_x, * = next_line[ileft]
        left_x_end = left_x + node.left.value.to_s.size
        print " " * (left_x_end - last_x)
        if left_x_end < x
          print " "
          print "_" * (x - left_x_end - 1)
          slashes << [left_x_end, '/']
        end
      else
        print " " * (x - last_x)
      end

      print text

      x += text.to_s.size

      if node.right
        next_line = canvas_lines[y + 1]
        iright = next_line.index {|nx, *| x <= nx }
        right_x, * = next_line[iright]

        if x < right_x
          print "_" * (right_x - x - 1)
          print " "
          slashes << [right_x - 1, '\\']
        end
        x = right_x
      end

      last_x = x
    end

    puts

    last_x = 0
    slashes.each do |x, char|
      print " " * (x - last_x)
      print char
      last_x = x + 1
    end
    puts unless slashes.empty?
  end
end

# ツリーの宣言を短く書くために定義
def Node(val, left=nil, right=nil)
  node = Node.new(val)
  node.left = left
  node.right = right
  node
end

tree = Node(9, Node(4, Node(2), Node(6)), Node(15, Node(12), Node(17)))
print_canvas tree.render(0)
print_canvas2 tree.render(0)
print_canvas2 tree.render(3)
print_canvas3 tree.render(1)
print_canvas3 tree.render(2)
print_canvas3 tree.render(3)
print_canvas3 Node(4, tree, tree).render(0)
print_canvas3 Node(4, tree, tree).render(1)
print_canvas3 Node(4, Node(9, tree, nil), tree).render(2)
print_canvas3 Node(4, tree, tree).render(3)