Allister Allister - 1 year ago 71
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

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

ben ='Ben')
tom ='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:

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 Source

Use a hash to store the data:

data = { |h, k| h[k] = k }

while !(line = gets.strip).empty?
    parent, child = { |value| data[value] }
    if !parent.left
        parent.left = child
    elsif !parent.right
        parent.right = child
        raise "#{parent.value} already has both a left and right child"
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download