If I understand the rules correctly, it can me implemented in O(N) in the following way:

1. Attach a second integer to each node
2. non-leaf node = 0, leaf node = node's main value.
3. Do a depth-first walk.
4. For every node that you visited all children of, set the second value to the sum of the second values of the direct children. If the second value is smaller than the main value, set it to the main value instead

(i adjusted 2nd leaf node from 15 to 10 for illustrative purposes)

After step 2.

          15
           0
   20            25
    0             0
5      10      5  
5      10      5  

After first non-leaf is visited:

          15
           0
   20            25
   15             0
5      10  
5      10      5  

15 is smaller so set it to 20

          15
           0
   20            25
   20             0
5      10      5  
5      10      5  

Final tree after algorithm:

          15
          45 <- answer
   20            25
   20            25
5      10      5  
5      10      5  

If I understand the rules correctly, it can me implemented in O(N) in the following way:

1. Attach a second integer to each node
2. non-leaf node = 0, leaf node = node's main value.
3. Do a depth-first walk.
4. For every node that you visited all children of, set the second value to the sum of the second values of the direct children. If the second value is smaller than the main value, set it to the main value instead

(i adjusted 2nd leaf node from 15 to 10 for illustrative purposes)

After step 2.

          15
           0
   20            25
    0             0
5      10      5  
5      10      5  

After first non-leaf is visited:

          15
           0
   20            25
-> 15 <-          0
5      10  
5      10      5  

15 is smaller so set it to 20

          15
           0
   20            25
   20             0
5      10      5  
5      10      5  

Final tree after algorithm:

          15
          45 <- answer
   20            25
   20            25
5      10      5  
5      10      5  

It can me implemented in O(N) in the following way:

1. Attach a second integer to each node
2. non-leaf node = 0, leaf node = node's main value.
3. Do a depth-first walk.
4. For every node that you visited all children of, set the second value to the sum of the second values of the direct children. If the second value is smaller than the main value, set it to the main value instead

(i adjusted 2nd leaf node from 15 to 10 for illustrative purposes)

After step 2.

          15
           0
   20            25
    0             0
5      10      5  
5      10      5  

After first non-leaf is visited:

          15
           0
   20            25
   15             0
5      10  
5      10      5  

15 is smaller so set it to 20

          15
           0
   20            25
   20             0
5      10      5  
5      10      5  

Final tree after algorithm:

          15
          45 <- answer
   20            25
   20            25
5      10      5  
5      10      5  

If I understand the rules correctly, it can me implemented in O(N) in the following way:

1. Attach a second integer to each node
2. non-leaf node = 0, leaf node = node's main value.
3. Do a depth-first walk.
4. For every node that you visited all children of, set the second value to the sum of the second values of the direct children. If the second value is smaller than the main value, set it to the main value instead

(i adjusted 2nd leaf node from 15 to 10 for illustrative purposes)

After step 2.

          15
           0
   20            25
    0             0
5      10      5  
5      10      5  

After first non-leaf is visited:

          15
           0
   20            25
   15             0
5      10  
5      10      5  

15 is smaller so set it to 20

          15
           0
   20            25
   20             0
5      10      5  
5      10      5  

Final tree after algorithm:

          15
          45 <- answer
   20            25
   20            25
5      10      5  
5      10      5