Find Maximum from a Tree

Question

I am trying to find the maximum number from a given tree:

(define-struct (Some T)
  ([value : T]))

(define-type (Option T)
  (U 'None (Some T)))

(define-type BST (U 'E Nd))

(define-struct Nd
  ([root : Integer]
   [lsub : BST]
   [rsub : BST]))

(: maxi : BST Integer -> Integer)
(define (maxi x acc)
  (match x
        ('E acc)
((Nd ro ls rs)
    (cond
      ((> ro acc) (maxi ls ro))
      (else
       (maxi rs acc))))))

The above quote does not work properly when I enter the following:

(maxi (Nd 1 (Nd 2 (Nd 4 (Nd 8 'E 'E) (Nd 9 'E 'E)) (Nd 5 'E 'E)) (Nd 3 (Nd 6 'E 'E) (Nd 7 'E 'E))) 0)

Can someone please help?

Thank you!

What is the expected output? What is the one returned? Did you try to [trace](https://docs.racket-lang.org/reference/debugging.html)? — coredump, Nov 10 '16 at 21:28
The whole point of such tree is that it would be sorted and thus the deepest right node will hold the maximum value, but your tree is not sorted so I think perhaps you example data is wrong. your code seem to follow the left if this node was larger than the parent and disregard the right nodes or just follow the right node disregarding the left. It makes no sense. — Sylwester, Nov 11 '16 at 00:46
(Doesn't lisp provide for [code comments](http://stackoverflow.com/a/6365579/3789665)?) `BST` as well as the `cond` seem to imply _binary search tree_, which the example constructed is not. — greybeard, Nov 11 '16 at 01:07

coredump · Answer 1 · 2016-11-11T00:12:12.617

So here is your test:

(maxi
   (Nd
      1
      (Nd 2
         (Nd 4
            (Nd 8 'E 'E)
            (Nd 9 'E 'E))
         (Nd 5 'E 'E))
      (Nd 3
         (Nd 6 'E 'E)
         (Nd 7 'E 'E)))
   0)

And here is what happens:

   acc  root   what to do?
  ---------------------------------
   0    1      go left with acc = root
   1    2      idem
   2    4      idem
   4    8      idem
   8    E      return 8

If you expect your input trees to satisfy the binary search tree property, stating that values on the left subtree are always greater than root and values of the right subtree are all smaller or equal, then your test tree is a malformed BST, since 9 is greater than 4.

By the way, if you had a BST, where would the maximal value be located?

If however the tree is just a random tree, then you have to compute the maximum of both subtrees and the root value before being able to determine the overall maximal value.

Basically, you want to do:

(tree-max (Nd root left right)) = (max root 
                                       (tree-max left) 
                                       (tree-max right))

If you want to do it recursively, you will encounter a problem in the base case because you will have to provide a maximal value for an empty leaf node: any value you will pick will make your code incorrect for a tree which contains values strictly below that value. Say you choose zero and compute the max of a tree with only strictly negative numbers, then zero is the wrong answer because it does not appear in the tree (what could you do?).

You can choose to use an accumulator instead of recursion, but in that case you will need two accumuators: the maximum so far and the list of subtrees to visit next. Basically you replace the call stack with a heap-allocated stack.

I can't currently test the following code, but here is a possible implementation:

(define tree-max (tree greatest todo)
  (match tree
    ('E greatest (if (null? todo) 
                 greatest
                 (tree-max (first rest) 
                           greatest 
                           (rest todo))
    ((Nd root left right) (tree-max left
                                    (max greatest root) 
                                    (cons right todo))))

but how do you compute the maximum of both subtrees? I thought I was doing that, but I am not able to figure out how to do this — testomg, Nov 10 '16 at 21:56
Look at the `cond`, you only descend into one of the branch, I'll make an edit. — coredump, Nov 10 '16 at 22:02

Find Maximum from a Tree

1 Answers1