Question

How to parse a table into a binary tree in Ruby

Answer 1

# ================================================================
# Parse a table of (id, name, parent_id) into a binary tree using
# the Left‑Child / Right‑Sibling representation.
#
# Why this representation?
# - The table describes a general tree (each node can have many children).
# - A binary tree requires each node to have at most two pointers.
# - left  -> first child
# - right -> next sibling
#
# This preserves the full structure while staying inside a binary tree model.
# ================================================================

# A single tree node
class Node
  attr_accessor :id, :name, :left, :right

  def initialize(id, name)
    @id   = id
    @name = name
    @left = nil   # first child
    @right = nil  # next sibling
  end
end

# ================================================================
# Print the tree with indentation and explicit ROOT markers
# ================================================================

def print_tree(node, depth = 0)
  return unless node

  # Print ROOT on its own line
  puts "ROOT" if depth == 0

  # Indent the node itself
  indent = "  " * (depth + 1)

  # Print ID with leading zero if needed
  puts "#{indent}#{format('%02d', node.id)} - #{node.name}"

  # First child
  print_tree(node.left, depth + 1)

  # Next sibling (another top-level node)
  if depth == 0
    print_tree(node.right, 0)  # restart ROOT
  else
    print_tree(node.right, depth)
  end
end

# ================================================================
# Build the tree using Left‑Child / Right‑Sibling representation
# ================================================================

def build_tree(table)
  # Create nodes
  nodes = {}
  table.each do |row|
    nodes[row[:id]] = Node.new(row[:id], row[:name])
  end

  root = nil

  # Attach children and siblings
  table.each do |row|
    id        = row[:id]
    parent_id = row[:parent_id]
    current   = nodes[id]

    if parent_id == 0
      # top-level node → sibling chain under root
      if root.nil?
        root = current
      else
        p = root
        p = p.right while p.right
        p.right = current
      end
    else
      parent = nodes[parent_id]

      # attach as first child or next sibling
      if parent.left.nil?
        parent.left = current
      else
        p = parent.left
        p = p.right while p.right
        p.right = current
      end
    end
  end

  root
end

# ================================================================
# Main Program
# ================================================================

table = [
  { id: 1,  name: "Node 1",        parent_id: 0 },
  { id: 2,  name: "Node 1.1",      parent_id: 1 },
  { id: 3,  name: "Node 2",        parent_id: 0 },
  { id: 4,  name: "Node 1.1.1",    parent_id: 2 },
  { id: 5,  name: "Node 2.1",      parent_id: 3 },
  { id: 6,  name: "Node 2.3.1",    parent_id: 3 },
  { id: 7,  name: "Node 1.2",      parent_id: 1 },
  { id: 8,  name: "Node 1.3",      parent_id: 1 },
  { id: 9,  name: "Node 1.3.1",    parent_id: 8 },
  { id: 10, name: "Node 2.4",      parent_id: 3 },
  { id: 11, name: "Node 2.1.1",    parent_id: 5 },
  { id: 12, name: "Node 2.1.1.6",  parent_id: 11 }
]

root = build_tree(table)
print_tree(root)


#
# run:
#
# ROOT
#   01 - Node 1
#     02 - Node 1.1
#       04 - Node 1.1.1
#     07 - Node 1.2
#     08 - Node 1.3
#       09 - Node 1.3.1
# ROOT
#   03 - Node 2
#     05 - Node 2.1
#       11 - Node 2.1.1
#         12 - Node 2.1.1.6
#     06 - Node 2.3.1
#     10 - Node 2.4
#

 

70+ SQL courses for beginners and professionals