find_longest_branch_in_a_tree.rb

require 'pry'

class Node
  attr_accessor :value, :left, :right, :name

  def initialize(options={})
    @value = options[:value]
    @name = options[:name]
  end

  def children
    [@left, @right].compact
  end

  def children?
    @left && @right
  end

  def no_children?
    @left.nil? && @right.nil?
  end
end

root = Node.new({:value => 1, :name => 'root'})
child_1 = Node.new({:value => 2, :name => 'child_1'})
child_2 = Node.new({:value => 3, :name => 'child_2'})
grand_child_1 = Node.new({:value => 4, :name => 'grand_child_1'})
grand_grand_child_1 = Node.new({:value => 5, :name => 'grand_grand_child_1'})
grand_child_1.left = grand_grand_child_1
child_1.left = grand_child_1
root.left = child_1
root.right = child_2

def maximum_branch(node)
  return [[], 0] if node.nil?

  left, length_l = maximum_branch(node.left)
  right, length_r = maximum_branch(node.right)

  length_l > length_r ? [left<<node, length_l+1] : [right<<node, length_r+1]
end

nodes, length = maximum_branch(root)
puts nodes.map(&:value)
puts length