max_path_sum.rb

#
# <Node tree=Array.new([value, left, right]) parent=Node node_index=(1|2)>
#
class Node < Struct.new(:tree, :parent, :node_index)
  def value
    @value ||= tree[0]
  end

  def leaf(index)
    tree[index] ? Node.new(Array(tree[index]), self, index) : nil
  end

  def left
    @left ||= leaf(1)
  end

  def right
    @right ||= leaf(2)
  end

  def direction
    node_index == 1 ? :left : :right
  end

  def leaf?
    !left && !right
  end
end

def max_consecutive_sum(arr)
  max = 0

  for i in (0..arr.length - 2) do
    for j in (i + 1..arr.length - 1) do
      val = arr[i..j].inject(:+)

      max = val > max ? val : max
    end
  end

  max
end

# All routes through the tree
def tree_paths(node, path = [], last_direction = nil)
  path += [node.value]

  paths = [path]

  return paths if node.leaf? && last_direction

  if node.left && ![:up_left, :up_right].include?(last_direction)
    paths += tree_paths(node.left, path, :left)
  end

  if node.right && last_direction != :up_right
    paths += tree_paths(node.right, path, :right)
  end

  if node.parent && ![:left, :right].include?(last_direction)
    paths += tree_paths(node.parent, path, "up_#{ node.direction }".to_sym)
  end

  paths
end

def tea_tree_leaves(node)
  leaves = []

  return [node] if node.leaf?

  leaves += tea_tree_leaves(node.left) if node.left

  leaves += tea_tree_leaves(node.right) if node.right

  leaves
end

def max_path_sum(tree)
  edges = tea_tree_leaves(tree)

  paths = edges.reduce([]) { |paths, edge| paths += tree_paths(edge) }

  paths.map { |path| max_consecutive_sum(path) }.max
end

binary_tree = Node.new([10, [3, 20, 1], [10, nil, [-20, 5, 2]]], nil)

puts max_path_sum(binary_tree)
# => 43