Allister Allister - 3 months ago 8
Ruby Question

Constructing a Ruby Binary Tree from String

A bit of a newbie to computing science.

I have the basics for a binary tree in Ruby:

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


This works fine if I construct it manually, for example, if I want
tom
to be a child node of
ben
:

ben = Node.new('Ben')
tom = Node.new('Tom')

ben.left = tom


One of the challenges I need to figure out is how to construct a tree for inputted parent/child pairs. Here is an example input string:

peter tom
peter marie
marie john
tom oscar


My binary tree would look something like this:

peter
|
tom marie
| |
oscar john


I am wondering if I can get some direction into converting multiple strings in the following format
"[parent] [child]"
into a binary tree.

Thanks :)

Answer

Use a hash to store the data:

data = Hash.new { |h, k| h[k] = Node.new k }

while !(line = gets.strip).empty?
    parent, child = line.split.map { |value| data[value] }
    if !parent.left
        parent.left = child
    elsif !parent.right
        parent.right = child
    else
        raise "#{parent.value} already has both a left and right child"
    end
end