1description = <<-DESC
  2Given a binary tree and a number k, your task is to find the sum of tree nodes at level k. 
  3The binary tree is represented by a string tree with the format: (<node-value>(<left subtree>)(<right subtree>)).
  4
  5Example
  6
  7For tree = "(0(5(6()())(14()(9()())))(7(1()())(23()())))" and k = 2, the output should be
  8
  9treeLevelSum(tree, k) = 44.
 10
 11Explanation: The nodes at level 2 are 6, 14, 1, and 23, so the answer is 6 + 14 + 1 + 23 = 44.
 12
 13Input/Output
 14
 15[time limit] 4000ms (rb)
 16[input] string tree
 17
 18A valid string representing a tree.
 19
 20Guaranteed constraints:
 21
 222 ≤ tree.length ≤ 105.
 23
 24All the values in a given tree are guaranteed to be integers.
 25
 26[input] integer k
 27
 28Guaranteed constraints:
 29
 300 ≤ k ≤ 105.
 31
 32[output] integer
 33
 34The total sum of all the values at level k in a tree.
 35
 36https://en.wikipedia.org/wiki/S-expression
 37DESC
 38
 39describe "tree_level_sum" do
 40  # parse s-expression
 41  def parse(tokens, values, offset = 0)
 42    struct = []
 43    while offset < tokens.length
 44      if "(" == tokens[offset]
 45        offset, items = parse(tokens, values, offset + 1)
 46        struct << items
 47      elsif ")" == tokens[offset]
 48        break
 49      else
 50        struct << values.shift
 51      end
 52      offset += 1
 53    end
 54
 55    return [offset, struct]
 56  end
 57
 58  def build_tree(string)
 59    tokens = string.gsub("(", " ( ").gsub(")", " ) ").split(" ")
 60    values = string.scan(/\d+/).map(&:to_i)
 61    _, tree = parse(tokens, values, 0)
 62    tree[0]
 63  end
 64
 65  def tree_level_sum(tree, target)
 66    tree = build_tree(tree)
 67    queue = [node: tree, level: 0]
 68    sum = 0
 69    until queue.empty?
 70      top = queue.shift
 71
 72      if top[:level] == target
 73        sum += top[:node][0]
 74      end
 75
 76      left = top[:node][1]
 77      right = top[:node][2]
 78      if left.size > 0
 79        queue.push(node: left, level: top[:level] + 1)
 80      end
 81      if right.size > 0
 82        queue.push(node: right, level: top[:level] + 1)
 83      end
 84    end
 85    sum
 86  end
 87
 88  def tree_level_sum(tree, target)
 89    # ( + level
 90    # ) - level
 91    # if level == target
 92    #   add number to sum
 93    level = -1
 94    sum = 0
 95    tokens = tree.gsub("(", " ( ").gsub(")", " ) ").split(" ")
 96    tokens.each do |token|
 97      if token == "("
 98        level += 1
 99      elsif token == ")"
100        level -= 1
101      elsif level == target
102        sum += token.to_i
103      end
104    end
105    sum
106  end
107
108  <<-EXAMPLE
109       0
110      / \
111     /   \
112    5     7
113   / \   / \
114  6  14 1  23
115       \
116        9
117
118  (0(5(6()())(14()(9()()))) (7(1()())(23()())))
119[0,
120  [ 5,
121    [6, [], [] ],
122    [14, [], [9, [], []]]
123  ],
124  [ 7,
125    [1, [], []],
126    [23, [], []]
127  ]
128]
129level 2: tree[1][1][0] + tree[1][2][0] + tree[2][1][0] + tree[2][2][0] = 44
130  EXAMPLE
131  [
132    {tree: "(0(5(6()())(14()(9()())))(7(1()())(23()())))", k: 2, expected: 44},
133    {tree: "(3(3()())(1()()))", k: 1, expected: 4},
134    {tree: "(0(5(6()())(4()(9()())))(7(1()())(3()())))", k: 2, expected: 14},
135    {tree: "(3()())", k: 0, expected: 3},
136    {tree: "(0(5()())())", k: 1, expected: 5},
137  ].each do |x|
138    it do
139      expect(tree_level_sum(x[:tree], x[:k])).to eql(x[:expected])
140    end
141  end
142end