class Node
  attr_accessor :value, :left, :right
  def initialize(val)
    @value = val   # ノードが保持する値
    @left = nil    # 左側のノード
    @right = nil   # 右側のノード
  end
end
 
# 描画に必要な情報を計算
def render_info(canvas, margin, node, x, y)
  # 左のノードがあれば、そのノード以下の木の横幅を計算
  x = render_info(canvas, margin, node.left, x, y + 1) + margin if node.left
 
  # このノードの分の描画に必要な情報(X座標, Y座標, そのもの)を追加
  canvas << [x, y, node]
 
  # このノードの桁数を計算
  x += node.value.to_s.size
 
  # 右のノードがあれば、そのノード以下の木の横幅を計算
  x = render_info(canvas, margin, node.right, x + margin, y + 1) if node.right
 
  # 呼び出した親のために横幅を返す
  x
end
 
# render_infoで描画情報を集めて返す
def render(root, margin=0)
  canvas = []
  render_info(canvas, margin, root, 0, 0)
  canvas
end
 
#    9
#  4    15
# 2 6 12  17
 
# このメソッドはクラス外でOK
def print_canvas(canvas)
  # X座標よりY座標を優先してソート
  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
 
    # y座標が増えたら改行
    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
 
#   _9__
#  4    15
# 2 6 12  17
 
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
       # 「次の行の数字で、この数字のすぐ左にあるもの」を探してX座標をとる
      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
      # 「次の行の数字で、この数字のすぐ右にあるもの」を探してX座標をとる
      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
 
#    9_
#   /  \
#  4    15
# 2 6 12  17
 
def print_canvas3(canvas)
  # Y座標ごとにグループ分け
  canvas_lines = canvas.group_by {|x, y, *| y }.sort.map {|_, line| line.sort }
 
  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 render(tree)
print_canvas2 render(tree)
print_canvas3 render(tree)
print_canvas3 render(Node(4, tree, tree))
print_canvas3 render(Node(4, tree, tree), 2)
print_canvas3 render(Node(4, Node(4), tree), 1)
 
# バグ: 右手にノードがないと落ちる
print_canvas3 render(Node(4, tree, nil), 1) rescue puts $!

Y2xhc3MgTm9kZQogIGF0dHJfYWNjZXNzb3IgOnZhbHVlLCA6bGVmdCwgOnJpZ2h0CiAgZGVmIGluaXRpYWxpemUodmFsKQogICAgQHZhbHVlID0gdmFsICAgIyDjg47jg7zjg4njgYzkv53mjIHjgZnjgovlgKQKICAgIEBsZWZ0ID0gbmlsICAgICMg5bem5YG044Gu44OO44O844OJCiAgICBAcmlnaHQgPSBuaWwgICAjIOWPs+WBtOOBruODjuODvOODiQogIGVuZAplbmQKIAojIOaPj+eUu+OBq+W/heimgeOBquaDheWgseOCkuioiOeulwpkZWYgcmVuZGVyX2luZm8oY2FudmFzLCBtYXJnaW4sIG5vZGUsIHgsIHkpCiAgIyDlt6bjga7jg47jg7zjg4njgYzjgYLjgozjgbDjgIHjgZ3jga7jg47jg7zjg4nku6XkuIvjga7mnKjjga7mqKrluYXjgpLoqIjnrpcKICB4ID0gcmVuZGVyX2luZm8oY2FudmFzLCBtYXJnaW4sIG5vZGUubGVmdCwgeCwgeSArIDEpICsgbWFyZ2luIGlmIG5vZGUubGVmdAogCiAgIyDjgZPjga7jg47jg7zjg4njga7liIbjga7mj4/nlLvjgavlv4XopoHjgarmg4XloLEoWOW6p+aomSwgWeW6p+aomSwg44Gd44Gu44KC44GuKeOCkui/veWKoAogIGNhbnZhcyA8PCBbeCwgeSwgbm9kZV0KIAogICMg44GT44Gu44OO44O844OJ44Gu5qGB5pWw44KS6KiI566XCiAgeCArPSBub2RlLnZhbHVlLnRvX3Muc2l6ZQogCiAgIyDlj7Pjga7jg47jg7zjg4njgYzjgYLjgozjgbDjgIHjgZ3jga7jg47jg7zjg4nku6XkuIvjga7mnKjjga7mqKrluYXjgpLoqIjnrpcKICB4ID0gcmVuZGVyX2luZm8oY2FudmFzLCBtYXJnaW4sIG5vZGUucmlnaHQsIHggKyBtYXJnaW4sIHkgKyAxKSBpZiBub2RlLnJpZ2h0CiAKICAjIOWRvOOBs+WHuuOBl+OBn+imquOBruOBn+OCgeOBq+aoquW5heOCkui/lOOBmQogIHgKZW5kCiAKIyByZW5kZXJfaW5mb+OBp+aPj+eUu+aDheWgseOCkumbhuOCgeOBpui/lOOBmQpkZWYgcmVuZGVyKHJvb3QsIG1hcmdpbj0wKQogIGNhbnZhcyA9IFtdCiAgcmVuZGVyX2luZm8oY2FudmFzLCBtYXJnaW4sIHJvb3QsIDAsIDApCiAgY2FudmFzCmVuZAogCiMgICAgOQojICA0ICAgIDE1CiMgMiA2IDEyICAxNwogCiMg44GT44Gu44Oh44K944OD44OJ44Gv44Kv44Op44K55aSW44GnT0sKZGVmIHByaW50X2NhbnZhcyhjYW52YXMpCiAgIyBY5bqn5qiZ44KI44KKWeW6p+aomeOCkuWEquWFiOOBl+OBpuOCveODvOODiAogIGNhbnZhcyA9IGNhbnZhcy5zb3J0X2J5IHt8eCwgeSwgKnwgW3ksIHhdIH0KIAogIGxhc3RfeCA9IDAKICBsYXN0X3kgPSAwCiAKICAjIOWQhOODjuODvOODieOCkuODq+ODvOODl+OBp+aPj+eUuwogIGNhbnZhcy5lYWNoIGRvIHx4LCB5LCBub2RlfAogICAgdGV4dCA9IG5vZGUudmFsdWUudG9fcwogCiAgICAjIHnluqfmqJnjgYzlopfjgYjjgZ/jgonmlLnooYwKICAgIGlmIHkgIT0gbGFzdF95CiAgICAgIGxhc3RfeCA9IDAKICAgICAgcHV0cwogICAgZW5kCiAKICAgICMg5b+F6KaB44Gq5YiG44Gg44GR44K544Oa44O844K544KS5YWl44KM44Gm44OX44Oq44Oz44OICiAgICBwcmludCAiICIgKiAoeCAtIGxhc3RfeCkKICAgIHByaW50IHRleHQKIAogICAgICAgICMg44Kr44O844K944Or44KS6YCy44KB44KLCiAgICBsYXN0X3ggPSB4ICsgdGV4dC50b19zLnNpemUKICAgIGxhc3RfeSA9IHkKICBlbmQKICBwdXRzCmVuZAogCiMgICBfOV9fCiMgIDQgICAgMTUKIyAyIDYgMTIgIDE3CiAKZGVmIHByaW50X2NhbnZhczIoY2FudmFzKQogIGNhbnZhcyA9IGNhbnZhcy5zb3J0X2J5IHt8eCwgeSwgKnwgW3ksIHhdIH0KIAogIGxhc3RfeCA9IDAKICBsYXN0X3kgPSAwCiAKICAjIOWQhOODjuODvOODieOCkuODq+ODvOODl+OBp+aPj+eUuwogIGNhbnZhcy5lYWNoIGRvIHx4LCB5LCBub2RlfAogICAgdGV4dCA9IG5vZGUudmFsdWUudG9fcwogCiAgICBpZiB5ICE9IGxhc3RfeQogICAgICBsYXN0X3ggPSAwCiAgICAgIHB1dHMKICAgIGVuZAogCiAgICBpZiBub2RlLmxlZnQKICAgICAgICMg44CM5qyh44Gu6KGM44Gu5pWw5a2X44Gn44CB44GT44Gu5pWw5a2X44Gu44GZ44GQ5bem44Gr44GC44KL44KC44Gu44CN44KS5o6i44GX44GmWOW6p+aomeOCkuOBqOOCiwogICAgICBpbGVmdCA9IGNhbnZhcy5pbmRleCB7fG54LCBueSwgKnwgeSArIDEgPT0gbnkgJiYgeCA8PSBueCB9IC0gMQogICAgICBsZWZ0X3gsICogPSBjYW52YXNbaWxlZnRdCiAgICAgIGxlZnRfeF9lbmQgPSBsZWZ0X3ggKyBub2RlLmxlZnQudmFsdWUudG9fcy5zaXplCiAgICAgIHByaW50ICIgIiAqIChsZWZ0X3hfZW5kIC0gbGFzdF94KQogICAgICBwcmludCAiXyIgKiAoeCAtIGxlZnRfeF9lbmQpCiAgICBlbHNlCiAgICAgIHByaW50ICIgIiAqICh4IC0gbGFzdF94KQogICAgZW5kCiAKICAgIHByaW50IHRleHQKIAogICAgeCArPSB0ZXh0LnRvX3Muc2l6ZQogCiAgICAjIOaVsOWtl+WPs+WBtOOBruS4i+e3mgogICAgaWYgbm9kZS5yaWdodAogICAgICAjIOOAjOasoeOBruihjOOBruaVsOWtl+OBp+OAgeOBk+OBruaVsOWtl+OBruOBmeOBkOWPs+OBq+OBguOCi+OCguOBruOAjeOCkuaOouOBl+OBpljluqfmqJnjgpLjgajjgosKICAgICAgaXJpZ2h0ID0gY2FudmFzLmluZGV4IHt8bngsIG55LCAqfCB5ICsgMSA9PSBueSAmJiB4IDw9IG54IH0KICAgICAgcmlnaHRfeCwgKiA9IGNhbnZhc1tpcmlnaHRdCiAKICAgICAgcHJpbnQgIl8iICogKHJpZ2h0X3ggLSB4KQogICAgICB4ID0gcmlnaHRfeAogICAgZW5kCiAKICAgIGxhc3RfeCA9IHgKICAgIGxhc3RfeSA9IHkKICBlbmQKICBwdXRzCmVuZAogCiMgICAgOV8KIyAgIC8gIFwKIyAgNCAgICAxNQojIDIgNiAxMiAgMTcKIApkZWYgcHJpbnRfY2FudmFzMyhjYW52YXMpCiAgIyBZ5bqn5qiZ44GU44Go44Gr44Kw44Or44O844OX5YiG44GRCiAgY2FudmFzX2xpbmVzID0gY2FudmFzLmdyb3VwX2J5IHt8eCwgeSwgKnwgeSB9LnNvcnQubWFwIHt8XywgbGluZXwgbGluZS5zb3J0IH0KIAogIGNhbnZhc19saW5lcy5lYWNoIGRvIHxsaW5lfAogICAgIyDmlpznt5rjga7mj4/nlLvjgpLoqJjmhrbjgZfjgabjgYrjgY/phY3liJcKICAgIHNsYXNoZXMgPSBbXQogCiAgICAjIOOBk+OBruihjOOBq+WxnuOBmeaVsOWtl+OCkuaPj+eUu+OBl+OBpuOBhOOBjwogICAgbGFzdF94ID0gMAogICAgbGluZS5lYWNoIGRvIHx4LCB5LCBub2RlfAogICAgICB0ZXh0ID0gbm9kZS52YWx1ZS50b19zCiAKICAgICAgIyDmlbDlrZflt6blgbTjga7kuIvnt5oKICAgICAgaWYgbm9kZS5sZWZ0CiAgICAgICAgbmV4dF9saW5lID0gY2FudmFzX2xpbmVzW3kgKyAxXQogICAgICAgIGlsZWZ0ID0gbmV4dF9saW5lLmluZGV4IHt8bngsICp8IHggPD0gbnggfSAtIDEKICAgICAgICBsZWZ0X3gsICogPSBuZXh0X2xpbmVbaWxlZnRdCiAgICAgICAgbGVmdF94X2VuZCA9IGxlZnRfeCArIG5vZGUubGVmdC52YWx1ZS50b19zLnNpemUKICAgICAgICBwcmludCAiICIgKiAobGVmdF94X2VuZCAtIGxhc3RfeCkKICAgICAgICBpZiBsZWZ0X3hfZW5kIDwgeAogICAgICAgICAgIyDkuIvnt5rjga7lt6bnq6/jgpLmrKDjgZHjgZXjgZvjgosgKOOCueODmuODvOOCueOBq+OBmeOCiykKICAgICAgICAgIHByaW50ICIgIgogICAgICAgICAgcHJpbnQgIl8iICogKHggLSBsZWZ0X3hfZW5kIC0gMSkKICAgICAgICAgICMg5pac57ea44Gu5o+P55S744KS5LqI57SEICjlt6bmiYvjg47jg7zjg4njgarjga7jgafjgrnjg6njg4Pjgrfjg6UpCiAgICAgICAgICBzbGFzaGVzIDw8IFtsZWZ0X3hfZW5kLCAnLyddCiAgICAgICAgZW5kCiAgICAgIGVsc2UKICAgICAgICBwcmludCAiICIgKiAoeCAtIGxhc3RfeCkKICAgICAgZW5kCiAKICAgICAgcHJpbnQgdGV4dAogCiAgICAgIHggKz0gdGV4dC50b19zLnNpemUKIAogICAgICAjIOaVsOWtl+WPs+WBtOOBruS4i+e3mgogICAgICBpZiBub2RlLnJpZ2h0CiAgICAgICAgbmV4dF9saW5lID0gY2FudmFzX2xpbmVzW3kgKyAxXQogICAgICAgIGlyaWdodCA9IG5leHRfbGluZS5pbmRleCB7fG54LCAqfCB4IDw9IG54IH0KICAgICAgICByaWdodF94LCAqID0gbmV4dF9saW5lW2lyaWdodF0KIAogICAgICAgIGlmIHggPCByaWdodF94CiAgICAgICAgICAjIOS4i+e3muOBruWPs+err+OCkuasoOOBkeOBleOBm+OCiyAo44K544Oa44O844K544Gr44GZ44KLKQogICAgICAgICAgcHJpbnQgIl8iICogKHJpZ2h0X3ggLSB4IC0gMSkKICAgICAgICAgIHByaW50ICIgIgogICAgICAgICAgIyDmlpznt5rjga7mj4/nlLvjgpLkuojntIQgKOWPs+aJi+ODjuODvOODieOBquOBruOBp+ODkOODg+OCr+OCueODqeODg+OCt+ODpSkKICAgICAgICAgIHNsYXNoZXMgPDwgW3JpZ2h0X3ggLSAxLCAnXFwnXQogICAgICAgIGVuZAogICAgICAgIHggPSByaWdodF94CiAgICAgIGVuZAogCiAgICAgIGxhc3RfeCA9IHgKICAgIGVuZAogCiAgICBwdXRzCiAgICAjIOaUueihjOOBl+OBpuaWnOe3muOCkuaPj+eUuwogICAgbGFzdF94ID0gMAogICAgc2xhc2hlcy5lYWNoIGRvIHx4LCBjaGFyfAogICAgICBwcmludCAiICIgKiAoeCAtIGxhc3RfeCkKICAgICAgcHJpbnQgY2hhcgogICAgICBsYXN0X3ggPSB4ICsgMQogICAgZW5kCiAgICBwdXRzIHVubGVzcyBzbGFzaGVzLmVtcHR5PwogIGVuZAplbmQKIAojIOODhOODquODvOOBruWuo+iogOOCkuefreOBj+abuOOBj+OBn+OCgeOBq+Wumue+qQpkZWYgTm9kZSh2YWwsIGxlZnQ9bmlsLCByaWdodD1uaWwpCiAgbm9kZSA9IE5vZGUubmV3KHZhbCkKICBub2RlLmxlZnQgPSBsZWZ0CiAgbm9kZS5yaWdodCA9IHJpZ2h0CiAgbm9kZQplbmQKIAp0cmVlID0gTm9kZSg5LCBOb2RlKDQsIE5vZGUoMiksIE5vZGUoNikpLCBOb2RlKDE1LCBOb2RlKDEyKSwgTm9kZSgxNykpKQpwcmludF9jYW52YXMgcmVuZGVyKHRyZWUpCnByaW50X2NhbnZhczIgcmVuZGVyKHRyZWUpCnByaW50X2NhbnZhczMgcmVuZGVyKHRyZWUpCnByaW50X2NhbnZhczMgcmVuZGVyKE5vZGUoNCwgdHJlZSwgdHJlZSkpCnByaW50X2NhbnZhczMgcmVuZGVyKE5vZGUoNCwgdHJlZSwgdHJlZSksIDIpCnByaW50X2NhbnZhczMgcmVuZGVyKE5vZGUoNCwgTm9kZSg0KSwgdHJlZSksIDEpCiAKIyDjg5DjgrA6IOWPs+aJi+OBq+ODjuODvOODieOBjOOBquOBhOOBqOiQveOBoeOCiwpwcmludF9jYW52YXMzIHJlbmRlcihOb2RlKDQsIHRyZWUsIG5pbCksIDEpIHJlc2N1ZSBwdXRzICQh