binary_tree_level_of_min_sum.dart

class Node {
  Node? left;
  Node? right;
  int value;

  Node({required this.value, this.left, this.right});
}

/*
Given a binary tree, return the level of the tree with minimum sum.
 */
int main() {
  var tree = Node(value: 5);
  tree.left = Node(value: 3);
  tree.left!.left = Node(value: 2);
  tree.left!.right = Node(value: 1);
  tree.right = Node(value: 15);
  tree.right!.left = Node(value: 1);
  tree.right!.right = Node(value: -30);

  /*
          5
      3       15
    2  1     1  -30

    min sum is level 2 (-26 sum)
   */

  print("Level of the nodes with min sum: ${findMinSum(tree)}");
  return findMinSum(tree);
}

int findMinSum(Node tree) {
  List sums = [];
  int level = 0;

  sumRunner(tree, sums, level);
  final minSum = sums.fold<int>(sums.first, (previousValue, element) {
      return previousValue < element ? previousValue : element;
  });
  return sums.indexOf(minSum);
}

void sumRunner(Node node, List sums, int level) {
  try {
    sums[level] += node.value;
  } catch (e) {
    sums.insert(level, node.value);
  }

  if (node.left != null) {
    sumRunner(node.left!, sums, level + 1);
  }

  if (node.right != null) {
    sumRunner(node.right!, sums, level + 1);
  }
}