Etude On A Binary Tree

April 25, 2017

We have today another in our occasional series of exercises on binary trees; the input tree need not necessarily be ordered or balanced:

Given a binary tree containing integers, find the sum of all nodes at an even distance from the root, less the sum of all nodes at an odd distance from the root.

For instance, given the binary tree shown below, the requested sum is 1 – 2 – 3 + 4 + 5 + 6 + 7 – 8 – 9 – 10 – 11 – 12 – 13 – 14 – 15 = -74:

           1
     2           3
  4     5     6     7 
 8  9 10 11 12 13 14 15

(I’m not an artist; you’ll have to imagine the lines connecting the various levels.)

Your task is to write a program to compute alternate sums and differences of the nodes of a binary tree. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2