## 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

### 9 Responses to “Etude On A Binary Tree”

1. Paul said

In Python.

```from util.tree_print import tree_print

class Node(object):
def __init__(self, value):
self.value, self.lft, self.rgt = value, None, None
def __str__(self): return str(self.value)

def binsum(node, fvalue=None, fchildren=None):
""" fvalue: function that returns the value of node
fchildren: function that returns the children of node
"""
s = fvalue(node)
for child in fchildren(node):
s -= binsum(child, fvalue, fchildren)
return s

root = Node(1)
root.lft = Node(5); root.rgt = Node(7)
node = root.lft
node.lft = Node(33); node.rgt = Node(88)
node = root.rgt
node.lft = Node(22); node.rgt = Node(44)

def children(node): return [x for x in (node.lft, node.rgt) if x]
def value(node): return node.value

tree_print(root, node_children=children)
print("sum is:", binsum(root, value, children))
```
```├── 1
│   ├── 5
│   │   ├── 33
│   │   └── 88
│   └── 7
│       ├── 22
│       └── 44
sum is: 176
```
2. Rutger said

Got up with this solution. Printing the tree could use some work though..

```class Node(object):
def __init__(self, value):
self.left = None
self.right = None
self.value = value

def __str__(self):
return str(self.value)

def print_the_tree(node, indent=0):
if node:
print("  "*indent+str(node.value))
print_the_tree(node.left, indent+1)
print_the_tree(node.right, indent+1)

def sum_even_odd(node):
if node:
return node.value - sum_even_odd(node.left) - sum_even_odd(node.right)
return 0

root = Node(1)
root.left = Node(2); root.right = Node(3)
node = root.left
node.left = Node(4); node.right = Node(5)
node = root.right
node.left = Node(6); node.right = Node(7)

node = root.left.left
node.left = Node(8); node.right = Node(9)
node = root.left.right
node.left = Node(10); node.right = Node(11)

node = root.right.left
node.left = Node(12); node.right = Node(13)
node = root.right.right
node.left = Node(14); node.right = Node(15)

print_the_tree(root)
print(sum_even_odd(root))
```
3. Jussi Piitulainen said
```def inorder(tree, *, m = 1):
if tree:
this, left, rite = tree
yield from inorder(left, m = -m)
yield m * this
yield from inorder(rite, m = -m)

print(sum(inorder((1,
(2,
(4, (8, (), ()), (9, (), ())),
(5, (10, (), ()), (11, (), ()))),
(3,
(6, (12, (), ()), (13, (), ())),
(7, (14, (), ()), (15, (), ())))))))
```
4. john said

C11:

``` #include <stdio.h> #include <stdlib.h>```

``` typedef struct btree {   int val;   struct btree *l, *r; } btree_s; btree_s *branch(int val, btree_s *l, btree_s *r); btree_s *leaf(int val); void free_btree_s(btree_s *bt); int etude(btree_s *bt); int main(int argc, char **argv) {   btree_s *bt = branch(1,                        branch(2,                               branch(4,                                      leaf(8),                                      leaf(9)),                               branch(5,                                      leaf(10),                                      leaf(11))),                        branch(3,                               branch(6,                                      leaf(12),                                      leaf(13)),                               branch(7,                                      leaf(14),                                      leaf(15))));   printf("The etude is %d.\n", etude(bt));   free_btree_s(bt);   exit(0); } btree_s *branch(int val, btree_s *l, btree_s *r) {   btree_s *bt = malloc(sizeof(btree_s));   if (bt == NULL) {     fprintf(stderr, "memory allocation error\n");     exit(1);   }   bt->val = val;   bt->l = l;   bt->r = r;   return bt; } btree_s *leaf(int val) {   return branch(val, NULL, NULL); } void free_btree_s(btree_s *bt) {   if (bt == NULL) {     return;   }      free_btree_s(bt->l);   free_btree_s(bt->r);   free((void*)bt); } int etude(btree_s *bt) {   if (bt == NULL) {     return 0;   } ```

```  return bt->val - (etude(bt->l) + etude(bt->r)); } ```

5. bavier said

Forth:

```: T ( t1 t2 v -- t)  HERE >R , , , R> ;
: L ( v -- t)  0 0 ROT T ;
: C ( t -- t1 t2)  CELL+ DUP @  SWAP CELL+ @ ;
DEFER SUM
: (SUM)  DUP IF
DUP @  SWAP C SUM SWAP SUM  + NEGATE +
ELSE DROP 0 THEN ;
' (SUM) IS SUM
: TEST ( -- t)
8  L 9  L 4 T  10 L 11 L 5 T  2 T
12 L 13 L 6 T  14 L 15 L 7 T  3 T
1 T ;
TEST SUM .
```
6. matthew said

Here’s a slightly different recursive solution in Haskell. Uses an accumulating parameter so one of the two recursive calls is in tail position:

```data T = N | T Int T T
scan0 (T n left right) m = scan1 left (scan1 right (m+n))
scan0 _ n = n
scan1 (T n left right) m = scan0 left (scan0 right (m-n))
scan1 _ n = n

t = (T 1
(T 2
(T 4 (T 8 N N)(T 9 N N))
(T 5 (T 10 N N)(T 11 N N)))
(T 3
(T 6 (T 12 N N) (T 13 N N))
(T 7 (T 14 N N) (T 15 N N))))

main = print(scan0 t 0) -- -74
```
7. matthew said

OK, here’s a fully tail recursive version, using a continuation function. Despite the superficial resemblance to the above, the tree is traversed in the opposite order – the second occurrences of scan1 and scan0 in the RHS are partial applications.
[\code]
scan0 (T n left right) k m = scan1 left (scan1 right k) (m+n)
scan0 _ k m = k m
scan1 (T n left right) k m = scan0 left (scan0 right k) (m-n)
scan1 _ k m = k m

main = print(scan0 t (\x->x) 0)
[/code]

8. matthew said

Ooops:

```scan0 (T n left right) k m = scan1 left (scan1 right k) (m+n)
scan0 _ k m  = k m
scan1 (T n left right) k m = scan0 left (scan0 right k) (m-n)
scan1 _ k m = k m

main = print(scan0 t (\x->x) 0)
```
9. MUMPS V1:

tree(1)=
tree(1,”left”)=2
tree(1,”right”)=3
tree(2)=
tree(2,”left”)=4
tree(2,”right”)=5
tree(3)=
tree(3,”left”)=6
tree(3,”right”)=7
tree(4)=
tree(4,”left”)=8
tree(4,”right”)=9
tree(5)=
tree(5,”left”)=10
tree(5,”right”)=11
tree(6)=
tree(6,”left”)=12
tree(6,”right”)=13
tree(7)=
tree(7,”left”)=14
tree(7,”right”)=15
tree(8)=
tree(9)=
tree(10)=
tree(11)=
tree(12)=
tree(13)=
tree(14)=
tree(15)=

MCL> type tree
tree ;New routine
;
n sum
s sum=0
d process(1,0,.sum)
w !,”Sum = “,sum
q
;
process (node,level,sum) ;
n dir
s sum=sum+\$s(level#2=0:node,1:-node)
f dir=”left”,”right” d
. i \$d(tree(node,dir)) d
. . d process(tree(node,dir),level+1,.sum)
q

MCL> d ^tree

Sum = -74