How to know if a binary tree is ordered scheme

Question

A binary tree is ordered if all its children are under the left branch that the data of the root and branch of the right age and, in turn, binary trees of the left and right branches are also sorted. Write the procedure (ordered-btree? btree) receiving a binary tree as argument and returns True if ordered and false if not.

How can I do this?

Answer 1

There are several ways to solve this problem. I'll assume that there are no repeated elements in the tree and that you have written helper procedures for testing whether a tree is empty, whether it's a leaf (that is, both left and right subtrees are empty), for returning the left and right subtrees, the value in each node, the minimum value in a tree and the maximum - these should be trivial to write. The first implementation follows closely the recursive definition mentioned in the question, but it's not very efficient:

(define (ordered-btree? btree)
        ; if the tree is empty or is a leaf
  (cond ((or (is-empty? btree) (is-leaf? btree))
         ; then it's sorted
         true)
        ; else if the right subtree is empty
        ((is-empty? (right-tree btree))
         ; then test whether the current node's value is greater than
         ; the left subtree's maximum, and advance recursion over left
         (and (> (node-value btree) (max-value (left-tree btree)))
              (ordered-btree? (left-tree btree))))
        ; else if the left subtree is empty
        ((is-empty? (left-tree btree))
         ; then test whether the current node's value is less than
         ; the right subtree's minimum, and advance recursion over right
         (and (< (node-value btree) (min-value (right-tree btree)))
              (ordered-btree? (right-tree btree))))
        ; otherwise if both subtrees are non-empty
        (else                           
         ; then perform the same tests as above for both subtrees
         (and (> (node-value btree) (max-value (left-tree btree)))
              (< (node-value btree) (min-value (right-tree btree)))
              (ordered-btree? (left-tree btree))
              (ordered-btree? (right-tree btree))))))

A second approach would be to obtain a list of the tree's values using an in-order traversal, and then check if the returned list is sorted. This is a more efficient solution, I'll outline it - once again assuming that the proper helper procedures are in place:

(define (ordered-btree? btree)
  (is-sorted?         ; check whether a list of values is sorted
   (inorder-traversal ; return the in-order traversal of a tree as a list
    btree)))          ; a binary search tree

Answer 2

You make a recursive procedure that returns true for empty or leaf node, false if either children are wrong order. A default case (if none of the previous hit) the result is the recursion of ordered-btree? on both children in an and form. eg. (and (ordered-btree? left-child) (ordered-btree? right-child))

Notice that true and false is not standard Scheme. #t and #f is.

Edit since Óscar posted code I'll post my buffer as well:

(define (tree-sorted? tree)
  (let ts-minmax ((tree tree) (minv -Inf.0) (maxv +Inf.0))    
    (or (tree-empty? tree)
        (let ((value (tree-value tree)))
          (and (<= minv value maxv)
               (ts-minmax (tree-left  tree) minv  value)
               (ts-minmax (tree-right tree) value maxv))))))

;; these are just to document how the tree is built up
(define (make-tree value left right) (list value left right))
(define tree-value car)
(define tree-left cadr)
(define tree-right caddr)
(define tree-empty? null?)
(define tree-empty '())

How it works is that whenever you process the left child you know you should never have any higher values than the current node. For the right child you should never encounter a lower value than the current node. maxv and minv narrows down to the only valid range as you traverse. As a starting point I use negative and positive infinitive making the root node have any value.