How to Solve ‘treeLevelSum’ in CodeFights

The Problem

Given a binary tree and a number k, your task is to find the sum of tree nodes at level k. The binary tree is represented by a string tree with the format: (<node-value>(<left subtree>)(<right subtree>)).

Example

For tree = "(0(5(6()())(14()(9()())))(7(1()())(23()())))" and k = 2, the output should be

treeLevelSum(tree, k) = 44.

Explanation: The nodes at level 2 are 6, 14, 1, and 23, so the answer is 6 + 14 + 1 + 23 = 44.

Input/Output

  • [time limit] 4000ms (py)
  • [input] string tree

    A valid string representing a tree.

    Constraints:

    2 ≤ tree.length ≤ 105.

    All the values in a given tree are guaranteed to be integers.

  • [input] integer k

    Constraints:

    0 ≤ k ≤ 105.

  • [output] integer

    The total sum of all the values at level k in a tree.

The Solution

Capture.PNG

The Explanation

 

What we need is to find where the level starts and ends. We can do this by counting the ‘(‘ and ‘)’s. Everytime we see a ‘(‘ we go one level deeper and ‘)’ goes back up. Then, if we are in the level we are looking for and the character is not a parenthesis, we count the number. Of course, if it is not a parenthesis, we need to make sure that we are storing the number correctly, it may be bigger than 1-digit numbers. So, we convert the chars to a number until we see a different character and add that to the sum. (This is to make sure we don’t add 2 and 3 to sum instead of 23).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s