Ahmed Ahmed Ahmed Ahmed - 6 months ago 8
Ruby Question

Binary Tree - How do I include the trunk in the final output?

Initial input = [7, 4, 9, 1, 6, 14, 10]

expected = [1, 4, 6, 7, 9, 10, 14]

And my output...

[4, 9, 1, 6, 14, 10]

I can't seem to figure out how to include the trunk object in my output array.

def insert_node(element,trunk)
if element < trunk.payload && trunk.left == nil
# Build node and place it on left of trunk
trunk.left = BinaryTree.new(element, nil, nil)
elsif element > trunk.payload && trunk.right == nil
# Build node and place it on right of trunk
trunk.right = BinaryTree.new(element, nil, nil)
elsif element < trunk.payload
# Update pointer
insert_node(element, trunk.left)
elsif element > trunk.payload
# Update pointer
insert_node(element, trunk.right)
end
end

def build_tree(array)
trunk = BinaryTree.new(array.first, nil, nil)
array.shift
output = []

array.each do |element|
# Insert each element
output << insert_node(element,trunk).payload
end

return output
end


And my BinaryTree implementation

class BinaryTree
attr_accessor :payload, :left, :right

def initialize(payload, left, right)
@payload = payload
@left = left
@right = right
end

end

Answer

You also need way to walk the tree:

class BinaryTree
  attr_reader :payload, :left, :right

  def initialize(payload, left = nil, right = nil)
    @payload = payload
    @left = left
    @right = right
  end

  def walk
    (left ? left.walk : []) + [payload] + (right ? right.walk : [])
  end

  def insert_node(element)
    if element < payload && left == nil
      # Build node and place it on left of trunk
      @left = self.class.new(element)
    elsif element > payload && right == nil
      # Build node and place it on right of trunk
      @right = self.class.new(element)
    elsif element < payload
      # Update pointer
      left.insert_node(element)
    elsif element > payload
      # Update pointer
      right.insert_node(element)
    end
  end

  def self.build_from_array(array)
    new(array.shift).tap do |trunk|
      array.each { |element| trunk.insert_node(element) }
    end
  end
end

input =  [7, 4, 9, 1, 6, 14, 10]
expected =  [1, 4, 6, 7, 9, 10, 14]
output = BinaryTree.build_from_array(input).walk
p output
p output == expected