Etude On A Binary Tree

April 25, 2017

As usual, we represent a binary tree as a triple of the value of a node and its two children. Thus, the sample problem is represented as:

(define xs '(1 (2 (4 (8 () ()) (9 () ()))
(5 (10 () ()) (11 () ()))) (3 (6 (12 () ())
(13 () ())) (7 (14 () ()) (15 () ())))))

It might help to indent that expression like this:

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

Like all functions on binary trees, this is easy if you think recursively:

(define (f xs)
  (if (null? xs) 0
    (- (car xs) (f (cadr xs)) (f (caddr xs)))))

And here is the solution of our sample problem:

> (f xs)
-74

You can run the program at http://ideone.com/rGqCjv.

I’m amused by some of the discussion at Career Cup. The top-voted solution has a for loop inside a while loop, and uses a queue to keep track of which nodes remain to be visited; it’s not immediately clear how the program works. The second-highest-rated solution uses global variables to keep track of the odd-level and even-level sums. Most of the solutions use recursion, but make it hard to keep track of what is going on. The clearest solution, similar to ours but in C, is down-voted to -1; if I was Amazon, that’s the only solution I would accept.

Advertisements

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

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

%d bloggers like this: